빅오(big-O) 표기법이란?

빅오(big-O) 표기법은 알고리즘의 시간과 공간 복잡도를 수학적으로 표현하는 표기법으로, 데이터나 사용자의 증가에 따른 알고리즘의 성능을 예측하기 위해 사용한다. 정확한 실제 처리시간을 측정하고자 하는 것이 아니라 대략적인 증가율을 예측하고자 하는 것이므로, 증가율에 미치는 영향이 고정되어 있는 상수는 과감히 버리는 것이 특징이다.

아래에서는 대표적인 몇 가지 빅오 표기법을 정리한다.

O(1)

const n = [0,1,2,3,4];

function fn1(n) {
  return n[0] === 0 ? true : false;
}

위 코드에서 n 의 길이가 얼마나 길어지든, 값이 얼마나 커지든 관계없이 fn 함수는 n의 0번째 인덱스만을 검색해서 boolean 결과값을 반환하므로 데이터의 크기와 무관하게 처리시간이 일정하다.
이 경우, fn 함수는 O(1)의 시간 복잡도를 가진다고 말할 수 있다.

O(n)

const n = [0,1,2,3,4];

function fn2(n) {
  for(let i = 0; i < n.length; i++) {
    console.log(n[i]);
  }
}

같은 논리로 fn2 함수를 살펴보면, n의 길이가 1개 늘어날 때마다 for문이 1회 더 돌아가므로 n 의 길이와 처리시간은 비례관계를 가진다고 볼 수 있을 것이다. 데이터(x축)와 처리시간(y축)의 관계는 우상향하는 직선을 그리게 되며, 이 함수는 O(n)의 시간 복잡도를 가진다.

O(n²)

const n = [0,1,2,3,4];

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

fn3 함수는 [n의 길이 x n의 길이] 만큼 반복문을 돌리므로 n의 길이에 따라 처리시간은 n의 제곱 만큼 증가한다. 데이터(x축)와 처리시간(y축)의 관계는 기울기가 체증하며 우상향하는 곡선을 그리게 되며, 이 함수는 O(n²)의 시간 복잡도를 가진다.

O(nm)

const n = [0,1,2,3,4];
const m = [0,1,2];

function fn4(n) {
  for(let i = 0; i < n.length; i++) {
    for(let j = 0; j < m.length; j++) {
      console.log(i + j);
    }
  }
}

fn4 는 Fn3 와 유사하지만 내부의 for문이 배열 m 의 길이만큼 돌아간다. fn3 와 달리 m의 길이는 n보다 길 수도 있고 짧을 수도 있으므로 함수의 처리시간에 n 외에 m도 영향을 미치게 된다. 그래프는 fn3와 마찬가지로 기울기가 체증하는 우상향의 곡선이 그려진다.

O(n³)

const n = [0,1,2,3,4];

function fn5(n) {
  for(let i = 0; i < n.length; i++) {
    for(let j = 0; j < n.length; j++) {
      for(let k = 0; k < n.length; k++) {
        console.log(i + j + k);
      }
    }
  }
}

O(n²)을 이해했다면 fn5의 연산횟수가 n의 길이 x n의 길이 x n의 길이, 즉 n의 세제곱만큼 발생한다는 것을 쉽게 받아들일 수 있을 것이다. n의 길이 증가에 따른 연산횟수가 O(n²)에 비해 더욱 급격히 증가하므로 데이터(x축)와 처리시간(y축)의 그래프상에서는 기울기가 더욱 가파르게 치솟는 우향상의 곡선이 그려진다.

O(2ⁿ)

// 피보나치 수열의 n번째 값을 반환하는 함수

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

위 함수에서 num의 크기가 1 커지면 재귀가 2번 돌아가며, 그 안에서 또 두번... 그 안에서 또 두번... 탈출조건이 성립할 때 까지 2의 n제곱만큼 연산이 돌아간다.

n이 20이라고 할 때 처리시간이 O(n³) 에서는 8,000 에 불과하지만 O(2ⁿ) 에서는 1,048,576 에 다다른다. 즉, 데이터(x축)와 처리시간(y축)의 그래프상에서 우상향하는 곡선의 기울기는 O(n³) 보다도 훨씬 더 가파르게 체증한다.

O(log n)

//아래 함수는 이진탐색 로직을 구성하고 있다.

function fn7(target, n) {

  let start = 0;
  let end = n.length - 1;
  
  while (start <= end) {
    let middle = n[Math.floor((start + end) / 2)];
  
    if (middle === target) {
      return true;
    } else if (middle > target) {
      end = middle - 1;
    } else {
      start = middle + 1;
    }
  }
  
  return false;
}

이진 탐색(Binary Search)이 O(log n)을 나타내는 대표적인 함수라고 할 수 있는데, 이는 up down 게임과 유사한 데이터 검색방법이다. 이진 탐색은 매우 큰 효율성을 갖춘 검색방식으로, 데이터량이 아무리 커져도 처리시간이 대동소이하다.

데이터의 중간값을 잡고 내가 검색하려는 값이 중간값보다 작으면 중간값보다 큰 데이터를 전부 버리고 절반으로 나뉜 데이터에서 다시 중간값을 잡고 이번엔 내 타겟값이 중간값보다 크다면 중간값 미만의 값을 가지는 데이터를 전부 버리고 다시 중간값을 잡고... 하는 방식으로 타겟을 찾아내는 방식이다. 이진 탐색을 공부해보지 않아서 무슨 말인지 낯설다면 위 예시코드를 직접 쳐보는게 최고다.