Big O notation

빅오표기법이란?

• 알고리즘의 시간 복잡도를 나타내는 표기법
• O(f(n))으로 나타내며, O(1) < O(logn) < O(n) < O(nlogn) < O(n^2) < O(2^n) 등의 순서로 복잡하다

알고리즘 내에서 간단하게 Big-O 계산하기

사실 일일이 단위 연산(primitive operation)을 세는 것은 의미가 없다.
루프 밖에 있는 단순 연산들은 결국 상수항이라 제외되고, 루프 안에 여러 개의 연산이 있다고 하더라도 가장 큰 차수 외에는 각 항의 계수를 포함한 모든 것들이 무시되기 때문에 루프와 recursion 횟수를 확인하는 것이 중요하다.
예를 들어, n에 관련된 for loop가 두 번 있다면 n에 대한 1차식 두 개를 곱하므로 n에 대한 2차식이 되고, 이는 O(n^2)이 된다.
결국 알고리즘 내에서 Big-O notation은 루프의 차수(깊이)와 직결된다고 볼 수 있다. 즉, n에 대한 loop가 1개라면 O(n), 두 개라면 O(n^2)이라고 할 수 있다.

시간복잡도 예제

const sum1 = (n) => {
  return n*n;
}

첫 번째 방법은 곱셈 연산 1개로 big-O 표기법으로 O(1) 이 된다.

const sum2 = (n) => {
  let sum = 0;
  for (let i = 1; i <= n; i++) {
    sum = sum + n;
  }
}

이 경우는 덧셈 연산 1개와 대입 연산 1개가 N만큼 실행되므로 2N의 시간이 걸리지만 big-O 표기법으로는 상수항을 무시하여 O(N) 이 된다.

const sum3 = (n) => {
  let sum = 0;
  for (let i = 1; i <= n; i++) {
    for (let j = 1; j <= n; j++) {
      sum = sum + 1;
    } 
  }
}

덧셈 연산, 대입 연산 이 각각 NxN번 실행되므로 총 2N²의 시간이 걸리지만 마찬가지로 상수항을 무시하여 big-O 표기법으로 O(N²) 이 된다.