알고리즘 - 시간복잡도

시간 복잡도

실행 환경과 메모리 사용량에 따라 프로그램의 성능은 다르기 때문에 성능을 정확하게 측정하는 것은 불가능합니다. 그렇기 때문에 대략적인 성능 비교를 위한 상대적 표기법인 빅오 표기법을 사용하기로 했습니다.

// O(log n) 로그시간
for(leti=0; i<=n; i*=2){
	// ...
}

// O(n) 선형시간
for(let i=0; i<n; i++){
	// ...
}

// O(n log n) 선형 지수 시간
for(let i=0; i<n; i++){
	for(let j=1; j<=n; j*=2){
		// ...
	}
}

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

// 지수시간이나 팩토리얼 시간 등의 코드는 특정한 상황이 아니면 가급적 사용하면 안 되는 코드이므로
// 작성하지 않았습니다

빅오 표기법에서 식의 계수가 있거나 상수를 더하고 빼는 것은 보신 적이 없을 것입니다. 그 이유는 빅오표기법은 점근적 표기법을 따르기 때문입니다. 점근적 표기법은 함수의 증감 추세를 비교하는 방법이기 때문입니다.

빅오 표기법에는 네 가지 법칙이 있습니다.

계수 법칙

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

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

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

합의 법칙

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++){
 // ...
}

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

곱의 법칙

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++){
	for(let i=0; i<n*5; i++){
		// ...
	}
}

다항 법칙

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

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

여러가지 법칙이 있지만 총 두 가지만 기억하면 됩니다. 상수항은 무시되며, 이진 탐색 가장 큰 항 외엔 무시된다는 것입니다.