Big O 표기법

하나의 함수를 구현하는 방법에는 여러가지가 있다.어떤 것이 가장 좋은 방법일까?

코드를 평가할 때 점수를 매기거나 great, pretty good, awful 등의 단어로 나타낼 수도 있겠지만, 모두 같은 기준을 가지고 코드의 효율을 판단하면 편리할 것이다.

1부터 n까지 1씩 늘어나는 숫자의 합을 구하는 함수를 작성해보자. 두 개의 예시가 있다.

solution 1

function add1(n) {
  let total = 0;
  for (let i = 1; i <= n; i++) {
    total += i;
  }
  return total;
}

console.log(addUpTo(6));
// 21

solution 2

function add2(n) {
  return n * (n + 1) / 2;
};

console.log(addUpTo(6))
// 21

어떤 것이 더 나은 코드일까? 그리고 더 낫다는 기준은 무엇일까?
더 빠른 코드? 메모리를 덜 사용하는 코드? 가독성이 좋거나 간결한 코드?

parformance.now()를 활용하여 브라우저 콘솔에서 함수 실행에 걸린 시간을 체크해본다.

let t1 = performance.now();
add1(10000000000);
let t2 = performance.now();
console.log(`Time Elapsed ${(t2 - t1) / 1000 } seconds.`)

// Time Elapsed 11.883799999952316 seconds.

let t1 = performance.now();
add2(10000000000);
let t2 = performance.now();
console.log(`Time Elapsed ${(t2 - t1) / 1000 } seconds.`)
// Time Elapsed 0.00010000002384185791 seconds.

두번째 함수의 실행 시간이 훨씬 짧은 것으로 나타난다.
그러나 시간을 정확히 측정하는 것은 이렇게 간단하지 않다. 왜냐하면

• 기기마다 따라 걸리는 시간이 다르다.
• 같은 기기에서도 매번 다르게 시간이 걸린다!
• 짧고 빠른 로직이면 더욱 더 걸리는 시간이 정확히 측정되지 않는다.

그러므로 시간을 재서 비교하는 것은 정확한 방법이 아니다.

그보다는 컴퓨터가 수행해야 하는 연산(operation)의 수가 더 정확한 기준이 된다.

function add1(n) {
  let total = 0; // [=] 1 assignment
  for (let i = 1; i <= n; i++) { 
    // [=] 1 assignment
    // [<=] n comparisons
    // [++] n additions and assignments
    total += i; 
    // [+=] n additions and assignments
  }
  return total;
}
// n이 10이면 52번의 연산이 일어난다. (5n + 2)

function add2(n) {
  return n * (n + 1) / 2;
  // [*] 1 multiplication 
  // [+] 1 addition
  // [/] 1 division 
};
// n 값에 관계 없이 총 3번의 연산이 일어난다. 

이 연산 횟수에 근거한 측정법을 기준으로, Big O 표기법은 알고리즘의 실행 속도가 input 크기에 따라 어떻게 증가하는지 표준화하여 논할 수 있게 해준다.

Big O 표기법과 시간 복잡도

---

Big O 표기법으로 알고리즘의 시간 복잡도를 나타내는 방법은 다음을 따른다.

Big O 표기법의 원형은 O(f(n))이며,

• f(n)이 선형적(linear)이면 f(n) = n 이므로 O(n)이 된다.
  (input size와 연산 횟수가 비례함을 뜻한다.)
• f(n)이 제곱(quadratic) 형식이면f(n) = n^2 이므로 O(n^2)이 된다.
• f(n)이 변하지 않는 상수이면 f(n) = 1 이고 O(1)이 된다.
• 이 외에도 다양한 표기법들이 있다.

add2 함수는 n 값에 비례하여 연산 횟수가 늘어나므로 Big O 표기법에 에 따른 시간 복잡도가 O(n)이다.

add2 함수는 n 값이 커져도 연산 횟수가 변하지 않으므로 O(1)이다.

function countUpAndDown(n) {
  console.log('Going up!');
  for (let i = 0; i < n; i ++) {
    console.log(i);
  }
  console.log('At the top! Going down...')
  for (let j = n - 1; j >= 0; j--) {
    console.log(j);
  }
  console.log('Back down. Bye!')
}

countUpAndDown(10)

두 개의 for 문이 있으므로 두 번의 O(n) 연산이 있지만, O(2n) 처럼 표기하지 않는다. 상수는 생략하고 O(n)으로 표기한다.

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

여기에도 2개의 loop가 있는데, O(n) 내부에 또 다른 O(n)이 있다.
이 경우 O(n * n)인 O(n^2)이 된다.

예시

---

function logAtLeast5(n) {
  for (var i = 1; i <= Math.max(5, n); i++) {
    console.log(i);
  }
}

function logAtMost5(n) {
  for (var i = 1; i <= Math.min(5, n); i++) {
    console.log(i);
  }
}

logAtLeast5의 시간 복잡도는 n의 증가와 연산 횟수가 비례하므로 O(n)이다.

logAtMost5에서는 n에 어떤 숫자가 들어가도 5까지만 출력 된다. 즉, input관계 없이 최대 5회의 loop이 발생한다. 그래프의 주된 궤적이 flat 하므로 O(1)이다.

Big O 표기법과 공간 복잡도

---

Big O 표기법으로 공간 복잡도도 나타낼 수 있다.

우선 자바스크립트에서 공간 복잡도를 나타낼 때

• 문자열을 제외한 원시값(booleans, numbers, undefined, null)은 constant space를 차지한다. 즉 input 값에 따라 달라지지 않는다.
• 문자열은 O(n)의 공간을 차지하며, n은 문자열의 길이이다.

function sum(arr) {
  let total = 0; // one number
  for (let i = 0; i < arr.length; i++) { // another number
    total += arr[i];
  }
  return total;
}

숫자를 담는 공간이 2개 있으며, 원시값 공간은 input에 따라 달라지지 않으므로 공간 복잡도는 O(1)이다.

function double(arr) {
  let newArr = [];
  for (let i = 0; i < arr.length; i++) {
    newArr.push(2 * arr[i]);
  }
  return newArr;// n numbers
}

input 배열의 길이에 따라 newArr에 저장되는 배열의 길이가 늘어나므로 O(n)이다.

🔗 JavaScript Algorithms and Data Structures Masterclass