시간 복잡도

Big-O notation (빅오표기법)

O(n) 예시

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

O(log n) 예시

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

O(n log n) 예시

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

O(n²) 예시

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

계수 법칙

• 상수 k가 0보다 클 때 f(n) = O(g(n)) 이면 kf(n) = O(g(n))이다.
  n이 무한에 가까울수록 k의 크기는 의미가 없기 때문이다.

// 두 루프는 같은 O(n)으로 표기된다.
for(let i = 0; i < n; i += 1) {
	// ...
}

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

합의 법칙

• f(n) = O(h(n))이고 g(n) = O(p(n))이면 f(n) + g(n) = O(h(n)) + O(p(n))이다.
  빅오는 더해질 수 있다.

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

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

곱의 법칙

• f(n) = O(h(n))이고 g(n) = O(p(n))이면 f(n) * g(n) = O(h(n)) * O(p(n))이다.
  빅오는 곱해질 수 있다.

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

다항 법칙

• f(n)이 k차 다항식이면 f(n)은 O(n^k)이다.

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

2가지만 기억하면 된다.

1. 상수항은 무시

// 계수 법칙에 의해 계수는 무시된다.
// 그리하여 O(n + m)으로 표기된다.
for(let i = 0; i < n * 6; i += 1) {
	// ...
}

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

2. 가장 큰 항 외엔 무시

// O(n^2 + n)이지만 작은 항은 무시하여
// O(n^2)으로만 표기해도 된다.
for(let i = 0; i < n; i += 1) {
	// ...
}

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

성능 측정 방법

const start = new Date().getTime();

// ...

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

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

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

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

↓ Output ↓

Start

1114

Finish