우리가 문제를 해결하기 위해 계획을 세울 때 어떤 알고리즘을 쓸 지 결정합니다. 사용할 알고리즘을 결정하면 제한시간 내에 답을 얻을 수 있는지 시간복잡도 분석을 해야합니다. 대부분의 알고리즘에서 가장 많은 시간을 차지하는 부분은 반복문입니다.

알고리즘의 종류

알고리즘의 종류는 크게 아래와 같이 나눌 수 있습니다.

• 선형 시간 알고리즘
• 선형 이하 시간 알고리즘
• 다항 시간 알고리즘
• 지수 시간 알고리즘

선형 시간 알고리즘

선형 시간 알고리즘의 수행 시간은 $N$에 정비례합니다. 만약 $N$이 두 배 커지면 실행 시간도 두 배 늘어납니다.

선형 이하 시간 알고리즘

선형 이하 시간 알고리즘의 대표적인 예는 이진 탐색입니다.

다항 시간 알고리즘

$N$이나 $N^2$ 등 $N$의 거듭제곱들의 선형 결합으로 이루어진 식들을 다항식이라고 부릅니다. 반복문의 수행 획수를 입력 크기의 다항식으로 표현할 수 있는 알고리즘들을 다항 시간 알고리즘이라고 부릅니다.
$N$, $N^2$은 물론 $N^9$도 다항식이므로 다항 시간 알고리즘에 포함되는 알고리즘 간에는 엄청나게 큰 시간 차이가 날 수 있습니다.

지수 시간 알고리즘

지수 시간 알고리즘은 N이 하나 증가할 때마다 걸리는 시간이 배로 증가하는 알고리즘입니다. 예를 들어 $2^N$이 있습니다.

O 표기

알고리즘의 시간 복잡도를 표현할 때는 보통 O 표기를 사용합니다. O 표기는 가장 빨리 증가하는 항만 남긴 채 나머지를 다 버리는 표기법입니다. 상수도 버립니다.
O 표기는 함수의 상한을 나타냅니다. 가장 빨리 증가하는 항만을 남기는데 어떻게 상한을 나타내는지 의문이 들 수 있지만, 여기에서의 상한의 의미는 약간 특이합니다. $N$에 대한 함수 $f(N)$이 주어질 때, $f(N)=O(g(N))$이라고 쓰는 것은 다음과 같은 의미입니다.

아주 큰 $N_0$와 $C(N_0, C \gt 0)$를 적절히 선택하면 $N_0 \le N$인 모든 $N$에 대해 $|f(N) \le C \times \mid g(N)\mid$이 참이 되도록 할 수 있다.

예를 들어 $N_0=1000, C=2$라고 하면 $N^2$과 $N^2+100*N+1$을 비교할 때 $C\times N^2=2,000,000$이고 $N^2 + 100\times N + 1=1,100,001$이므로 항상 $N^2$이 더 크다고 할 수 있습니다.
다만, O 표기법은 수행 시간의 상한을 나타낼 뿐 최악의 수행 시간과 관련이 있지 않습니다. 예를 들어 퀵 정렬의 최악의 수행 시간은 $N^2$이지만, 평균 시간복잡도는 $O(N\lg N)$입니다.

시간 복잡도의 분할 상환 분석

분할 상환 분석을 이용하면 일반적으로는 시간이 오래 걸려 실행하지 못할 것이라고 여겼던 작업이 시간 안에 돌아가는 것을 이해할 수 있습니다.
우리가 보통 알고리즘의 시간 복잡도를 측정하는 방법은 최악의 경우를 고려하고, 이때의 시간/공간 비용을 고려하는 것입니다. 이렇게 했을 때 어떤 연산이 다른 연산에 비해서 시간이 많이 든다면 정확하게 측정하기 힘듭니다. 하지만 필요한 연산들의 시간 총합을 잴 수 있다면 더 정확하게 측정할 수 있습니다.
여기서 주의해야 할 점은 평균적인 시간 복잡도와는 다릅니다. 분할 상환 분석은 최악의 경우를 분석하는 것은 같지만, 최악의 경우에 드는 시간을 보다 엄밀하게 재는 방법입니다.
분할 상환 분석을 사용했을 때 좋은 예는 이진카운터나 스택의 연산 횟수, 동적 배열의 연산 횟수 측정입니다.

참고문헌: 구종만, 프로그래밍 대회에서 배우는 알고리즘 문제해결전략, 인사이트, (2012)