빅오표기법

시간복잡도를 나타내는 표기법 중 하나로 'O(입력)'으로 표기합니다.

빅오로 표현할 수 있는 시간복잡도의 코드는 아래와 같습니다.

1. O(1)

'일정한 복잡도'라고 하며, 입력값의 크기와 관계없이 즉시 출력값을 얻어낼 수 있는 시간복잡도 입니다.

function O_1_algorithm(arr, index) {
  console.log('o1 알고리즘!');
}

코드와 같이 함수 파라미터를 통한 입력값을 통해 바로 출력값을 얻었을 때 시간복잡도가 O(1)입니다.

2. O(n)

'선형 복잡도'라고 하며, 입력값이 증가함에 따라 시간 또한 같은 비율로 증가하는 것을 의미하는 시간복잡도 입니다.

function O_n_algorithm(n) {
  for (let i = 0; i < n; i++) {
    console.log(i)
  }
}

코드와 같이 n=1이면 i=0일 때 1초 실행시간, i=1일때 1초 실행시간, 이렇게 n이 1씩 증가할 때마다 실행시간이 1초씩 증가합니다.

즉, 입력값이 증가함에 따라 시간 또한 같은 비율로 늘어나는 시간복잡도가 O(n)입니다.

3. O(n^2)

'2차 복잡도'라고 하며, 입력값이 증가함에 따라 시간이 n의 제곱수 비율로 증가하는 것을 의미하는 시간복잡도 입니다.

입력값이 1일 때 1초의 실행시간이 걸리던 알고리즘에 3일 때 9초가 걸리는 것을 의미합니다.

function O_n2_algorithm(n) {
  for (let i = 0; i < n; i++) {
    for (let j = 0; j < n; j++) {
      console.log(i, j)
    }
  }
}

n=3이라고 한다면 i=0,1,2 j=0,1,2 총 9회의 for문이 돌아가고 총 실행시간이 9초이다.

이처럼 입력값이 증가함에 따라 시간이 제곱으로 증가하는 시간복잡도가 O(n^2)입니다.

4. O(2^n)

'기하급수적 복잡도'라고 하며, 가장 느린 시간 복잡도를 가집니다.

이 시간복잡도의 가장 대표적인 알고리즘은 피보나치 수열입니다.

function O_2n_algorithm(n){
  if(n <= 0) {
  	return 0;
  } else if(n === 1) {
  	return 1;
  }
  	return O_2n_algorithm(n-1) + O_2n_algorithm(n-2);
}

즉 함수를 호출할 때마다 바로 전 숫자와 그 전 숫자를 알아야 숫자를 더하면서 앞으로 나올 숫자를 파악할 수 있습니다. 이렇게 매번 함수가 호출될 때마다 두 번씩 호출합니다. 이걸 트리의 높이만큼 반복합니다.

5. O(log n)

해당 시간복잡도는 한번 처리할 때마다 탐색량이 절반씩 줄어듭니다.

let arr = [];

function O_logn_algorithm(k, s, e){
  for(let i = s; i <= e; i++){
    arr.push(i);
	let m = (s+e)/2;
    
    if(arr[m] === k){
      console.log(m) 
    } else if(arr[m]> k){
      return log(k, s, m-1);
    } else{
      return log(k, m+1,e)
    }
  }
}

해당 시간복잡도의 가장 대표적인 알고리즘은 이진 탐색입니다. 배열에서 특정 숫자를 찾을 때, 이진 탐색을 이용한다면 배열 가운데 값과 키값을 비교하고 가운데 값이 키값보다 작다면 탐색하지 않습니다. 그럼 다시 또 중간값을 설정하고 비교합니다.

6. O(n log n)

해당 시간복잡도는 퀵 정렬, 병합 정렬과 같은 분할 정복 정렬 알고리즘의 실행 시간입니다.

function O_nlogn_algorithm(arr) {
  if (arr.length <= 1) return arr;

  const pivot = arr[0];
  const left = [];
  const right = [];

  for (let i = 1; i < arr.length; i++) {
    if (arr[i] <= pivot) left.push(arr[i]);
    else right.push(arr[i]);
  }

  const lSorted = quickSort(left);
  const rSorted = quickSort(right);
  return [...lSorted, pivot, ...rSorted];
};

이전 문제에 있었던 퀵 정렬을 예로 들어보겠습니다. 기준값이 되는 피벗 포인트를 설정하고 해당 값보다 작은 배열, 큰 배열이 나뉘고 또 그 배열안에서 기준값을 정하고 해당 값보다 작은 배열, 큰배열 이렇게 분할 정복으로 계속 나뉘게 됩니다.

이 때의 시간복잡도가 O(n log n)입니다.