[알고리즘] Big O 표기법

카테고리 : 컴퓨터 공학
태그: cs · 컴퓨터 공학 · algorithm · BigO 표기법 · 시간 복잡도 · 공간 복잡도 · Logarithm

1. Big O

  • 같은 기능을 구현하는데도 여러 가지 접근 방법이 있다.
  • 무엇이 최선인지, 코드의 성능(perforamance)을 비교하는 방법
  • 코드의 성능에 대해 정확한 어휘로 말할 수 있는 것이 중요하다.
  • 더 좋은 코드 :
    • 브라우저에 내장된 timer를 사용.
    • 시간 측정 문제
      • 컴퓨터나 브라우저 사양에 따라 다른 시간이 기록될 수 있다.
      • 같은 머신도 다른 시간을 매번 측정할 수 있다.
    • 메모리를 최소화
    • 가독성이 좋은 방식
  1. console.time 으로 타이머 사용
function addUpTo(n) {
  let total = 0;
  for (let i = 1; i <= n; i++) {
    total += i;
  }
  return total;
}
console.time('timer');
console.log(addUpTo(10000000000));
console.timeEnd('timer');

[Running] node "/workspaces/codespaces-blank/bigo.js"
//50000000000067860000
//timer: 10.786s

//시간복잡도가 훨씬 낮음

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

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

[Running] node "/workspaces/codespaces-blank/bigo.js"
//50000000005000000000
//timer: 0.101ms
  1. 브라우저 빌트인 타이머
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(`경과 시간: ${(t2 - t1) / 1000} seconds.`);

//500000000067109000
//경과 시간: 1.0429085229998454 seconds.

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

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

console.log(`경과 시간: ${(t2 - t1) / 1000} seconds.`);

//50000000005000000000
//경과 시간: 0.00009833399998024106 seconds.

2. 시간 복잡도

Time complexity

  • BigO는 광범위한 추세만 보기에 상수는 중요하지 않다.
O(2n) ❌O(n) 🅾️
O(500) ❌O(1) 🅾️
O(13n²) ❌O(n²) 🅾️

3. 공간 복잡도

Space Complexity

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

3. Logarithm 시간 복잡도

logarithmic Complexity

  • 로그 사용 용도
    • 특정 검색 알고리즘에는 로그 시간 복잡도와 관련된다.
    • 효율적인 정렬 알고리즘에는 로그가 관련있다.
    • 재귀는 때때로 로그 공간 복잡도와 관련이 있다.

4. 정리

  • 알고리즘의 성능을 분석하기 위해 우리는 Big O를 사용함
  • 알고리즘의 시간 또는 공간 복잡성에 대한 고수준 이해를 제공할 수 있습니다.
  • 정확도에 대해서는 신경 쓰지 않으며, Big O는 광범위한 추세 (선형? 이차? 상수?)에만 관심을 둠.
  • 측정된 시간 또는 공간 복잡성은 알고리즘 자체에만 의존하며, 알고리즘을 실행하는 하드웨어와는 무관함.
  • 어디서나 사용되므로 많은 연습이 필요함.