[JS 알고리즘&자료구조] Big O에 대한 공식 소개

드디어 빅오의 추상적인 개념이 아닌 정확히 빅오가 무엇인지 살펴보자. 

  1. 숫자를 세는 것을 공식화한 것
  2. 입력 값이 늘어날수록 알고리즘의 실행 시간이 어떻게 변하는지 설명하는 공식적인 방식
    (입력 값과 실행 시간의 상관 관계를 표시)

앞 장에서 우리는 addUpToFirst는 입력 값 n에 따라 실행 시간이 선형적으로 계속 증가하는 것을 볼 수 있었고 addUpToSecond 함수는 입력 값 n과는 무관하게 실행 시간이 거의 0에 수렴하는 것을 볼 수 있었다. 이렇게 입력값과 실행 시간 간의 상관 관계를 시각화 하는 것을 Big O라고 할 수 있다.

Big O의 결과는 크게 4가지로 볼 수 있다.

1. O(n) : 실행 시간이 입력 값과 선형적 비례를 이룬다. (예시 : addUpToFirst)  

예시 코드를 하나 보도록 하자.

function countUpAndDown(n) {
  console.log("Going up!");
  for (var i = 0; i < n; i++) { // O(n)
    console.log(i);
  }
  console.log("At the top!\nGoing down...");
  for (var j = n - 1; j >= 0; j--) { // O(n)
    console.log(j);
  }
  console.log("Back down. Bye!");
}

위의 countUpAndDown 함수의 코드를 보면 2개의 for문이 입력 값에 따라 연산이 증가하는 O(n)이라고 볼 수 있는데 이 경우 countUpAndDown에 대한 Big O 표기법이 O(2n)이라고 헷갈릴 수 있으나 그냥 O(n)으로 표기한다.

2. O(n²) : 실행 시간이 입력 값의 제곱이 된다.

예시 코드를 보자.

function printAllPairs(n) {
 // O(n)이 중첩되어 존재하므로 O(n*n)이며 이는 O(n²)로 나타낼 수 있다.
  for (var i = 0; i < n; i++) { // O(n)
    for (var j = 0; j < n; j++) { // O(n)
      console.log(i, j);
    }
  }
}

위의 printAllPairs 코드에서는 2개의 for문이 중첩되어 존재하는 것을 확인할 수 있다. 이는 O(n²)으로 나타낸다. O(n²)에 해당하는 함수들은 실행 시간이 n²으로 늘어나는 것도 확인할 수 있다.

3. O(1) : 실행 시간이 입력 값과 무관하게 상수이다. (예시 : addUpToSecond)

4. 실행 시간이 완전히 다르게 나타날 수 있다. (이는 나중에 천천히 살펴보도록 하자)