자바스크립트 코딩테스트 - 시간 복잡도

시간복잡도

알고리즘의 성능을 나타내는 지표로, 입력 크기에 대한 연산 횟수의 상한을 의미합니다.
시간 복잡도는 낮을수록 무조건적으로 좋습니다.

시간복잡도를 측정하는 방법

시간 복잡도는 최악의 경우 기준으로 시간 복잡도를 분석합니다.
만약 n^4의 시간 복잡도를 가진 알고리즘도 첫번째 연산에서 문제가 해결된다면, 좋은 알고리즘 처럼 보일 수 있다. 알고리즘을 실행했을 때, 최악의 경우를 기준으로 판단을 하여야한다.

연산횟수가 아닌 추이를 활용한다.
위에 언급했듯이 정확한 연산의 횟수만 비교하는 것은 의미가 없다. 연산횟수의 추이를 확인하여, 점근적 표현을 해야한다.

빅오 표기법

상한성을 활용하여 점근적 표기를 하는 빅오표기법
특정 알고리즘의 연산횟수가 f(x)라면 최고차항을 제외한 모든 계수를 지워 O(...)형식으로 표현하는 것을 빅오 표기법이라고 합니다.

f(x)가 x^2 + 5x + 1이라면 O(x^2)라고 표기합니다.

x보다 x^2가, 지수보다는 다항함수가 빨리, 로그함수는 다항함수보다 천천히 증가하는 추이를 가지기 때문에 최고차항만 표기하는 것입니다.

대략적인 복잡도별 최대 연산 횟수

시간 복잡도	최대 연산 횟수
O(N!)	10
O(2^n)	20 ~ 25
O(N^3)	200 ~ 300
O(N^2)	3000 ~ 5000
O(NlogN)	100만
O(N)	1000 ~ 2000만
O(logN)	10억

시간 복잡도를 활용하여 문제가 제시하는 시간을 만족하도록 코드를 작성하면 됩니다.

시간복잡도 예시

별찍기 문제 : O(N^2)
박테리아 수명 문제 (반감기) : O(logN)