[Algorithm] Big O Notation

알고리즘을 사용할 때 크게 중요한 것이 두가지가 있다.

• Space Complexity (memory)
• Time Complexity (speed)

Big O

Big O는 알고리즘내에서 Time/Space의 효율성을 따질 때 사용하는 표기법이다. n값(input)이 무한대로 커졌을 때 알고리즘의 효율성이 얼마나 좋은지 판별하기 위해서 사용된다. 우리는 Big O를 사용해서 알고리즘의 런타임 성장정도를 대략적인 패턴으로 파악할 수 있다.

Big O는 위의 사진과 같이 6개로 구분되어진다. 주로 사용되는 대표적인 Big O는 아래와 같다.

O(1) Constant

input의 값이 아무리 커져도 Time/Space Complexity에는 영향을 미치지 않는 경우이다. 아래 예시의 경우, 항상 3개의 operation이 실행된다. (*, +, /)

• push pop
• Object.hasOwnProperty

const addUpTo = (n) => {
  return n * (n + 1) / 2;
}

O(n) Linear

input의 값이 커지면 Time/Space Complexity도 증가한다.

• shift unshift concat slice splice
• forEach map filer reduce
• Object.keys Object.values Object.entries

const addUpTo = (n) => {
  let total = 0;
  for (let i=1; i<=n; i++) {
    total += i;
  }
  return total; 
}

O(log n) Logarithm

O(n) < O(log n) < O(n^2)이라고 볼 수 있다. 주로 searching, sorting 알고리즘 혹은 recursion에 사용된다.

• sort

O(n^2) Quadratic

O(n*n)(2의 2승)과 같다. 아래 예시과 같이 중접된 for loop과 같은 경우이다.

const printAllPairs = () => {
  for(let i=0; i<n; i++) {
    for(let j=0; j<n; j++) {
      console.log(i, j);
    }
  }
}