시간복잡도(Time Complexity)

코딩테스트 연습을 하다보면 가끔 효율성테스트가 존재합니다.
이는 알고리즘의 로직을 코드로 구현할때 입력값(N)의 변화에따라 연산 회수에 비해
어느정도의 시간이 소요되는지 나타냅니다.

우리는 프로그램의 성능을 정확히 알 수 있을까요?

프로그램의 성능을 파악하기 위해서는 고려할 것들이 있습니다.
입력의 크기, 하드웨어 성능, 운영체제 성능, 컴파일러 최적화, etc.
이를 바탕으로 별도의 성능측정 프로그램을 작성하더라도 정확한 결과를 얻기 힘듭니다.
실행환경과 메모리 사용량에 따라 다른 결과가 나올 수 있기 때문입니다.

이때 주로 사용되는것이 빅오 표기법(Big-O notation) 입니다.
Big-O 표기법은 대략적인 성능을 비교하기위한 상대적인 표기법 인데요
알고리즘의 최악의 상황을 고려하여 실행 시간을 표기합니다.

Big-O 표기법

시간 복잡도의 성능을 비교하면 다음과 같습니다.

(왼쪽에서 오른쪽으로 갈수록 효율성이 떨어진다.)

예를들어 n = 1024일때,
O(n)은 1024번의 루프를 돌게되고 O(logn)은 10번의 루프를 돌게됩니다.

Big-O 표기법의 법칙

계수 법칙

상수 k가 0보다 클때 n이 무한에 가깔울 수록 k의 크기는 의미가 없어진다.

// 두 루프는 같은 O(n)의 시간복잡도를 갖는다.
for (let i = 0; i < n; i++) {
  // ...
}

for (let i = 0; i < n * 5; i++) {
  // ...
}

합의 법칙

Big-O는 서로 더해질 수 있다.

// 두 루프를 합쳐 O(n + m)으로 표기할 수 있다.
// 계수 법칙에 따라 5는 사라진다.
for (let i = 0; i < n; i++) {
  // ...
}

for (let i = 0; i < m * 5; i++) {
  // ...
}

곱의 법칙

Big-O는 서로 곱해질 수 있다.

// 두 루프를 곱해 O(n^2)으로 표기할 수 있따.
// 계수 법칙에 의해 5는 사라진다.
for (let i = 0; i < n; i++) {
  for (let j = 0; j < m * 5; j++) {
    // ...
  }
}

다항 법칙

f(n)이 k차 다항식이면 O(n^k)의 시간 복잡도를 갖는다.

// 다음 루프는 O(n^3)의 시간 복잡도를 갖는다.
for (let i = 0; i < n * n * n; i++) {
  // ...
}

JavaScript에서 성능 측정방법

Date 객체 이용

console.log("Start");
const start = new Date().getTime();
const N = 1000000000;

let total = 0;
for (let i = 0; i < N; i++) {
  total += i;
}

const end = new Date().getTime();
console.log(end - start);
console.log("Finish");

 ------------------output--------------------
Start
1306 // 1306ms = 약 1.3초
Finish