시간 복잡도

시간 복잡도란, 알고리즘의 성능을 나타내는 지표로, 입력 크기에 따른 연산 횟수를 의미한다. 당연히 낮으면 낮을수록 좋다.

시간 복잡도를 측정하는 기준은 최선 best, 보통 normal, 최악 worst의 경우로 나눌 수 있다. 코딩 테스트에서는 최악의 경우를 기준으로 하여 문제를 분석해야 한다.

충분히 큰 입력값 N에 따른 연산 횟수의 추이를 활용해서 시간 복잡도를 표현하는 방법을 점근적 표기법이라고 한다.

점근적 표기법 중에서도 상한선을 활용하여 시간 복잡도를 표기하는 방법을 빅오 표기법 big-O notation이라고 한다. 어떤 프로그램의 연산 횟수가 f(x)라고 할 때 함수의 최고차항을 남기고 계수를 지워 O(…)라고 표기한다.

$f(x)=2x^2+3x+5$
$O(x^2)$

코딩 테스트 문제에는 제한 시간이 있으므로 문제를 분석한 후에 빅오 표기법을 활용하여 해당 알고리즘을 적용했을 때 제한 시간 내에 출력값이 나올 수 있을지 가늠해 볼 수 있다. 보통은 다음을 기준으로 알고리즘을 선택한다.

컴퓨터가 초당 연산할 수 있는 최대 횟수는 보통 1억 번이다.

하지만 실제 코딩테스트에서는 이보다 여유를 둬야 통과할 수 있으므로, 제한 시간이 1초일 때 연산 횟수는 3000만이 초과하지 않도록 하는 것이 좋다.

제한 시간이 1초인 문제에 각 시간 복잡도 별로 허용할 수 있는 최대 연산 횟수

시간 복잡도	최대 연산 횟수
$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억