시간복잡도(Time Complexity)란?

시간 복잡도란 특정 알고리즘이 어떤 문제를 해결하는데 걸리는 시간을 의미합니다. 같은 결과를 가져오는 프로그래밍 소스도 어떻게 작성하느냐에 따라 걸리는 시간이 달라질 수 있습니다. 같은 결과를 나타내는 소스라면 최대한 시간이 적게 걸리는 좋은 소스입니다. 그렇기에 더 효율적인 알고리즘을 구성하기 위해서 시간 복잡도의 측면을 고려하고 중요하게 봅니다.

  O(1) < O(log n) < O(n) < O(n log n) < O(n^2) < O(2^n) < O(n!)
  상수시간 < 로그시간 < 선형시간 < 선형로그시간 < 이차시간 < 지수시간 < 팩토리얼 시간

log의 밑은 2 (컴퓨터 과학에서 밑을 생략하면 2라고 생각하면 된다.)

시간복잡도별 자바스크립트 예시

n = 3;

// O(log n)
for (let i = 0; i < n; i *= 2) {
  // ...
}

// O(n)
for (let i = 0; i < n; i += 1) {
  // ...
}

// O(n log n)
for (let i = 0; i < n; i += 1) {
  for (let j = 0; j < n; j *= 2) {
    // ...
  }
}

// O(n^2)
for (let i = 0; i < n; i += 1) {
  for (let j = 0; j < n; j += 1) {
    // ...
  }
}

// O(2^n), O(n!): 이 이상으로 가는 것은 좋지 않다고 생각함.

// 다음 루프는 O(n^3)으로 표기할 수 있다.
for (let i = 0; i < n * n * n; i += 1) {
  // ...
}

성능 측정 방법

const start = new Date().getTime();
console.log('Something...');
const end = new Date().getTime();
console.log(end - start);