알고리즘의 기초 Big-O Notation과 복잡도(Complexity)

Big-O Notation

Big-O는 알고리즘의 효율성을 나타내는 지표로서 알고리즘의 시간 복잡도와 공간 복잡도에 사용하며, 불필요한 연산들을 제거하고 알고리즘 분석을 쉽게 할 목적으로 사용된다.

 

시간복잡도와 공간복잡도

• 시간 복잡도(Time Complexity): 입력된 N의 크기에 따라 실행되는 조작의 수를 나타낸다.
• 공간 복잡도(Space Complexity): 알고리즘이 실행될 때 사용하는 메모리의 양을 나타낸다.

 

각 Big-O 표기법에 대한 시간복잡도(Time Complexity) 

Big-O는 다양한 실행시간이 존재하여, 다양하게 표현되지만, 가장 대표적인 표기법을 나열했다.

 

O(1) 시간 복잡도 Constant time

입력 데이터의 크기에 상관없이 일정한 시간이 걸리는 알고리즘의 시간복잡도를 표현할때 사용한다.

function printElement(arr) {
  console.log(`First element of array is ${arr[0]}`)
  return null
}

위의 예제처럼 함수에 아무리 크거나 작은 크기의 데이터를 인자로 받아도 실행시간은 동일하게 유지된다. 

 

O(n) 시간 복잡도 Linear time

입력 데이터의 크기에 비례해서 처리시간도 늘어나는 알고리즘의 시간복잡도를 표현할때 사용한다.

 

function printElement(arr) {
  for(let i = 0; i < arr.length; i++) {
     console.log(`First element of array is ${arr[0]}`)
  }
  return null
}

인자를 다양한 크기의 데이터를 전달받아 실행 할 경우 데이터의 크기에 맞추어 실행 시간이 정비례하게 증가한다.

 

O(n^2) 시간복잡도 Quadratic Time

입력 데이터의 크기의 제곱만큼 처리시간이 걸리는 알고리즘을 표현할 때 사용한다. 대표적인 예시로 버블 정렬 알고리즘이다.

 

function bubbleSort(arr) {
  for(let i = 0; i < arr.length; i++){
   for(let j = i+1; j < arr.length; j++){
      if(arr[i] > arr[j]) {
        let temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
      }
    }
  }
  return arr;
}

버블 정렬은 인접한 요소를 비교한다. 첫 번째 요소와 두번째 요소를 비교하여 두번쨰 요소보다 크면 서로 교환하고, 배열의 끝에 도달할 때까지 계속 반복한다. 

 

O(C^n) 시간 복잡도 Expontential time

실행 시간이 기하급수적으로 증가한다. 피보나치 수열을 표현할 경우 해당 시간 복잡도로 표현한다.

 

function fibonacci(num) {
  if(num <= 1) {
    return num;
  }
  return fibonacci(num - 2) + fibonacci(num - 1);
}

피보나치 수열을 재귀로  표현했으며 입력 크기가 추가 될 때 마다 두 배로 증가하는 알고리즘이다.

 

O(n log n) 시간 복잡도 linearithmic time 

로그 선형 알고리즘은 선형(linear) 알고리즘보다 약간 느리다. O(n log n)의 대표적인 예로 병합 정렬 알고리즘이다. 

 

/* 
*  mergedSort 함수는 주어진 배열을 정렬하고 
*  요소가 2개 이하가 될 때 까지 배열을 재귀적으로 나누고, 분할된 배열을 재귀적으로 정렬한다.
*/
function mergedSort(arr) {
  if(arr.length === 1) {
    return arr;
  }
  let middle = Math.floor(arr.length / 2);
  let left = mergeSort(arr.slice(0, middle));
  let right = mergeSort(arr.slice(middle));
  
  return merge(left, rigtht);
}
/*
* 함수 merge는 각 배열에서 하나씩 가져와서 오름차순으로 병합한다.
*
*/

function merge(arr1, arr2) {
  let i = 0;
  let j = 0;
  let result = [];
  
  while(i < arr1.length && j < arr2.length) {
    if(arr[i] < arr2[j]){ 
      result.push(arr1[i]);
      i++
    } else {
      result.push(arr2[j]);
      j++
    }
  }
  
  while(i < arr1.length) {
    result.push(arr[i])
    i++
  }
  
  while(j < arr2.length) {
    result.push(arr[j])
    j++
  }
  return result;
}

 

 

O(log n) 시간 복잡도 Logarithmic algorithm

O (log n) 알고리즘에선 대표적으로 이진탐색(Binary Search) 알고리즘이 존재한다. 

 

function binarySearch(arr, val) {
  let start = 0;
  let end = arr.length -1;
  
  while(start <= end) {
    let middle = Math.floor((start + end) / 2);
    if(arr[middle] === val)  {
      return middle;
    }else if(arr[middle] < val) {
      start = middle + 1;
    }else {
      end = middle -1;
    }
  }
  return -1
}

 위 예제 이진탐색은 주어진 요소의 중간을 찾아 원하는 자료와 비교하여 일치하는 항목이 발견되면 검색이 성공하고 종료된다. 

둘이 일치하지 않을 경우 원하는 자료보다 크거나 작은 경우를 반환하는 알고리즘이다. 결국 일치하는 요소를 찾을 때까지 동일한 절차를 반복하게 된다.

 

Big-O 계산 규칙

Big-O의 계산은 4가지 규칙을 따른다. 

1. Worst Case

2. Remove Contants

 

3.

 

4.

 

 

Big-O 자료 구조 별 복잡도

자료 구조	시간 복잡도
	평균				최악
	접근	검색	삽입	삭제	접근	검색	삽입	삭제
배열(Array)	O(1)	O(n)	O(n)	O(n)	O(1)	O(n)	O(n)	O(n)
스택(Stack)	O(n)	O(n)	O(1)	O(1)	O(n)	O(n)	O(1)	O(1)
큐(Queue)	O(n)	O(n)	O(1)	O(1)	O(n)	O(n)	O(1)	O(1)
단일 연결리스트 (Singly-Linked List)	O(n)	O(n)	O(1)	O(1)	O(n)	O(n)	O(1)	O(1)
이중 연결 리스트 (Doubly-Linked List)	O(n)	O(n)	O(1)	O(1)	O(n)	O(n)	O(1)	O(1)
해쉬 테이블 (Hash Table)	-	O(1)	O(1)	O(1)	-	O(n)	O(n)	O(n)
이진 탐색 트리 (Binary Search Tree)	O(log n)	O(log n)	O(log n)	O(log n)	O(n)	O(n)	O(n)	O(n)
비(B)-트리	O(log n)	O(log n)	O(log n)	O(log n)	O(log n)	O(log n)	O(log n)	O(log n)
레드-블랙 트리	O(log n)	O(log n)	O(log n)	O(log n)	O(log n)	O(log n)	O(log n)	O(log n)
AVL 트리	O(log n)	O(log n)	O(log n)	O(log n)	O(log n)	O(log n)	O(log n)	O(log n)

 

Big-O 정렬 알고리즘 복잡도

정렬 알고리즘	최적	평균	최악	메모리	동일값 순서 유지	비고
버블 정렬	O(n)	O(n^2)	O(n^2)	O(1)	yes
삽입 정렬	O(n)	O(n^2)	O(n^2)	O(1)	yes
선택 정렬	O(n^2)	O(n^2)	O(n^2)	O(1)	yes
힙 정렬	O(n log n)	O(n log n)	O(n log n)	O(1)	yes
병합 정렬	O(n log n)	O(n log n)	O(n log n)	O(n)	yes
퀵 정렬	O(n log n)	O(n log n)	O(n^2)	O(log n)	No	추가 내용
셀 정렬	O(n log n)	간격 순서에 영향	O(n (log n)^2)	O(1)	yes
계수 정렬	O(n + r)	O(n + r)	O(n + r)	O(n + r)	yes	r - 배열 내 가장 큰 수
기수 정렬	O(n * k)	O(n * k)	O(n * k)	O(n + k)	yes	k - 키 값의 최대 길이

 

*추가내용: 퀵 정렬은 보통 제자리(in-place)로 O(log n)스택 공간으로 수행된다. 

 

 

ref: "Esakkimuthu E의 알고리즘","Tim Roberts Big-O-Notation","benoitvallon Blog cheat chart","JS Algorithm GitHub"