[JS 알고리즘] Big O표기법

Udemy에서 Colt Steele의 JavaScript Algorithm & Data Structures MasterClass를 수강하면서 정리한 내용입니다.

Big O

• 같은 기능을 구현하는데도 여러 가지 접근 방법이 있다.
• 무엇이 최선인지, 코드의 성능(perforamance)을 비교하는 방법
• 코드의 성능에 대해 정확한 어휘로 말할 수 있는 것이 중요하다.
• 코드가 느리거나 충돌할 때, 문제가 발생할 수 있는 부분을 찾아내는 데 유용하다.
• 더 좋은 코드는 무엇인가?
  • 더 빠른?
    • 브라우저에 내장된 timer를 사용하여 속도를 잴 수 있다.
    • 시간 측정의 문제
      • 컴퓨터나 브라우저 사양에 따라 다른 시간이 기록될 수 있다.
      • 같은 머신도 다른 시간을 매번 측정할 수 있다.
  • 메모리를 덜 쓰는?
  • 가독성이 좋은?

Timing Our Code

• console.time 으로 타이머 사용
  • 아래 코드처럼 반복문 대신 공식을 사용하여 연산한 결과, 시간복잡도가 낮았음을 확인할 수 있다.

function addUpTo(n) {
  let total = 0;
  for (let i = 1; i <= n; i++) {
    total += i;
  }
  return total;
}
console.time('test');
console.log(addUpTo(10000000000));
console.timeEnd('test');

//50000000000067860000
//test: 7.596s

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

console.time('test');
console.log(addUpTo(10000000000));
console.timeEnd('test');

//50000000005000000000
//test: 3.998ms

• 브라우저 빌트인 타이머
  • 확실히 반복문은 입력값이 커질수록 느려지는 것이 확인된다. 반면에 공식은 아무리 수가 커져도 속도가 항상 빠르다.

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

let t1 = performance.now();
console.log(addUpTo(1000000000));
let t2 = performance.now();

console.log(`Time Elapsed: ${(t2-t1) / 1000} seconds.`)
//50000000000067860000
//Time Elapsed: 7.5107000000001864 seconds.

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

let t1 = performance.now();
console.log(addUpTo(10000000000));
let t2 = performance.now();

console.log(`Time Elapsed: ${(t2 - t1) / 1000} seconds.`);
//50000000005000000000
//Time Elapsed: 0.00009999999962747097 seconds.

• 시간의 문제
  • 다른 컴퓨터는 동일한 코드에 대해서도 다른 시간을 기록할 수 있다.
  • 같은 컴퓨터도 다른 시간을 매번 기록할 수 있다.
  • 빠른 알고리즘에게는 속도 측정이 충분히 정확하지 않을 수도 있다.
• 코드에 타이밍을 설정해보지 않더라도, 시간복잡도와 같은 효율성을 이해할 수 있는 방법이 있다.
  - Big O 표기법

• Performance Tracker로 각 알고리즘의 시간복잡도를 시각화하여 확인해볼 수 있다.
  - Performance Tracker

• Big O 정의

• BigO는 입력이 증가할 때마다 알고리즘의 런타임이 어떻게 증가하는지에 대하여 형식적으로 설명할 수 있게 해준다. 디테일은 신경 쓰지 않고 오직 광범위한 경향만 본다.

시간 복잡도

Time complexity

• BigO는 광범위한 추세만 보기에 상수는 중요하지 않다.
  

공간 복잡도

Space Complexity

• 자바스크립트에서 공간 복잡도 (경험 법칙, Rules of Thumb)
  • 대부분의 원시 값(boolean, number, undefined, nulls)들은 정해진 공간을 동일하게 갖는다.(숫자가 아무리 크거나, true나 false라고 해도)
  • String은 O(n)의 공간을 요구한다.(String의 길이가 n이다)
  • 참조 값들은 일반적으로 O(n)의 공간을 갖는다.(Array는 길이가 n이고, Obejct에서는 key들의 개수가 n이다.)

Logarithm 시간 복잡도

• Log는 지수(exponentiation)의 역수(inverse)이다.
  - 나눗셈과 곱셈이 쌍인 것처럼 로그와 지수도 쌍이다.
  

• The logarithm of a number roughly measures the number of times you can divide that number by 2 before you get a value that's less than or equal to one.

  • 로그는 어떤 숫자에 대하여 2로 나누면서 1이하의 값을 얻게 될때까지 걸리는 횟수를 대략적으로 측정한 숫자를 의미한다.
    

• 로그는 언제 사용하나?
  • Certain searching algorithms have logarithmic time complexity. Efficient sorting algorithms involve logarithms. Recursion sometimes involves logarithmic space complexity.
    • 특정 검색 알고리즘에는 로그 시간 복잡도와 관련된다.
    • 효율적인 정렬 알고리즘에는 로그가 관련있다.
    • 재귀는 때때로 로그 공간 복잡도와 관련이 있다.

• (참고)자료구조와 알고리즘 시각화 사이트 https://visualgo.net/ko