빅오 표기법

시간복잡도

입력값의 변화에 따라 연산을 실행할 때, 연산 횟수에 비해 시간이 얼마만큼 걸리는가?

효율적인 알고리즘을 구현한다는 것은 바꾸어 말해 입력값이 커짐에 따라 증가하는 시간의 비율을 최소화한 알고리즘을 구성했다는 이야기입니다.

그리고 이 시간 복잡도는 주로 빅-오 표기법을 사용해 나타냅니다.

빅오 표기법

빅오(Big-O) 표기법은 알고리즘의 최악의 경우 복잡도를 측정한다 ⇒ 입력값의 변화에 따라 연산을 실행할 때, 연산 횟수에 비해 시간이 얼마만큼 걸리는가?(O(n))

빅오 표기법에서 n은 입력의 개수를 나타낸다

빅오는 알고리즘의 효율을 분석하고 비교하는 데 중요하다

우선 빅오를 분석하기 위해서는 코드를 살펴보고 빅오 표기법을 단순화하고자 다음과 같은 자주 사용되는 법칙들을 적용해야 한다

계수/상수 제거하기(계수 법칙)
빅오 더하기(합의 법칙)
빅오 곱하기(곱의 법칙)
루프를 조사해 빅오 표기법의 다항 결정하기(다항 법칙)

O(1)

O(1) 는 constant complexity라고 하며 입력값이 증가하더라도 시간이 늘어나지 않습니다

// O(1)의 시간복잡도를 가지는 예시
function O_1_algorithm(arr, index) {
  return arr[index];
}

let arr = [1, 2, 3, 4, 5];
let index = 1;
let result = O_1_algorithm(arr, index);
console.log(result); // 2

위 알고리즘에선 입력값의 크기가 아무리 커져도 즉시 출력값을 얻어낼 수 있습니다

O(n)

O(n) 는 linear complexity라고 부르며 입력값이 증가함에 따라 시간 또한 같은 비율로 증가하는 것을 의미합니다

function O_n_algorithm(n) {
  for (let i = 0; i < n; i++) {
    // do something for 1 second
  }
}

function another_O_n_algorithm(n) {
  for (let i = 0; i < 2n; i++) {
    // do something for 1 second
  }
}

예를 들어 입력값이 1일 때 1초의 시간이 걸리고, 입력값을 100배로 증가시켰을 때 1초의 100배인 100초가 걸립니다

O(log n)

O(log n) 는 logarithmic complexity라고 부르며 Big-O 표기법중 O(1) 다음으로 빠릅니다

BST와 같은 로직입니다

BST에선 원하는 값을 탐색할 때, 노드를 이동할 때마다 경우의 수가 절반으로 줄어듭니다. up & down을 예로 들 수 있습니다.

1~100 중 하나의 숫자를 플레이어1이 고른다 (30을 골랐다고 가정합니다).
50(가운데) 숫자를 제시하면 50보다 작으므로 down을 외친다.
1~50중의 하나의 숫자이므로 또다시 경우의 수를 절반으로 줄이기 위해 25를 제시한다.
25보다 크므로 up을 외친다.
경우의 수를 계속 절반으로 줄여나가며 정답을 찾는다.

O(n2)

O(n2) 는 quadratic complexity라고 부르며 입력값이 증가함에 따라 시간이 n의 제곱수의 비율로 증가하는 것을 의미합니다

function O_quadratic_algorithm(n) {
  for (let i = 0; i < n; i++) {
    for (let j = 0; j < n; j++) {
      // do something for 1 second
    }
  }
}

function another_O_quadratic_algorithm(n) {
  for (let i = 0; i < n; i++) {
    for (let j = 0; j < n; j++) {
      for (let k = 0; k < n; k++) {
        // do something for 1 second
      }
    }
  }
}

예를 들어 입력값이 1일 경우 1초가 걸리던 알고리즘에 5라는 값을 주었더니 25초가 걸리게 된다면, 이 알고리즘의 시간 복잡도는 O(n2)라고 표현합니다.

O(2n)

O(2n) 은 exponential complexity라고 부르며 Big-O 표기법중 가장 느립니다

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

재귀로 구현하는 피보나치 수열은 O(2n)의 시간 복잡도를 가진 대표적인 알고리즘입니다. 브라우저 개발자 창에서 n을 40으로 두어도 수초가 걸리는 것을 확인할 수 있으며, n이 100 이상이면 평생 결과를 반환받지 못할 수도 있습니다