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

 Udemy 'JavaScript 알고리즘 & 자료구조 마스터클래스' 강좌를 바탕으로 작성한 글입니다.
 

Big O 표기법

같은 기능을 구현하는데도 여러 가지 접근 방법이 있다.

무엇이 최선인지 , 코드의 성능(performance)을 비교하는 방법 , 코드의 성능에 대해 정확한 어휘로 말할 수 있는 것이 중요하다.
코드가 느리거나 충돌할 때 , 문제가 발생할 수 있는 부분을 찾아내는 데 유용하다!

• 더 좋은 코드는 무엇인가 ?

  • 더 빠른?
    • 브라우저에 내장된 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

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

---

시간 복잡도

Time complexity

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

---

공간 복잡도

Space Complexity

• 자바스크립트에서 공간 복잡도(경험 법칙 , Rules of Thumb)
  • 대부분의 원시 값(boolean , number , undefined, nulls)들은 정채진 공간을 동일하게 갖는다.
    (숫자가 아무리 크거나 true나 false라고 해도)
  • String은 O(n)의 공간을 요구한다(String의 길이가 n이다)
  • 참조 값들은 일반적으로 O(n)의 공간을 갖는다.(Array는 길이가 n이고, Object에서는 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.
  • 특정 검색 알고리즘에는 로그 시간 복잡도와 관련된다.
  • 효율적인 정렬 알고리즘에는 로그가 관련있다.
  • 재귀는 때때로 로그 공간 복잡도와 관련이 있다.
    (참고) 자료구조와 알고리즘 시각화 사이트