[Algorithm] 재귀 알고리즘의 시간 복잡도 계산

저번 글에서는 시간 복잡도가 무엇인지와 시간 복잡도를 표현하는 점근적 표기법에 대해 알아봤습니다. 이번 글에서는 구조가 복잡한 재귀 알고리즘의 시간 복잡도를 어떻게 계산하는지 살펴봅시다.

 

• 자료구조, 알고리즘 시리즈 모아보기

 

재귀 알고리즘

`재귀 알고리즘`은 어떤 문제를 해결할 때 크기가 더 작은 동일한 문제를 해결해 얻은 답을 이용하는 알고리즘입니다. 말로 풀어 설명하는 것보다 직접 보는 게 더 이해가 쉬우실 겁니다. 대표적으로 팩토리얼과 피보나치 수열이 있습니다.

1. 팩토리얼

입력 n이 주어졌을 때 $n!$을 계산하는 함수를 $f_{actorial}(n)$이라고 합시다.

$$\begin{align*}f_{actorial}(5)&=5\times f_{actorial}(4)\\&=5\times4\times f_{actorial}(3)\\&=5\times4\times3\times f_{actorial}(2)\\&=5\times4\times3\times2\times f_{actorial}(1)\\&=5\times4\times3\times2\times1\end{align*}$$

위처럼 $f_{actorial}(5)$는 $f_{actorial}(4)$를 이용해서 계산하고, $f_{actorial}(4)$는 $f_{actorial}(3)$을 이용해서 계산합니다.

점화식으로 표현하면 다음과 같습니다.

$$f_{actorial}(0)=1\\[0.5em]f_{actorial}(n)=n\times f_{actorial}(n-1)$$

2. 피보나치수열

입력 n이 주어졌을 때 n번째 피보나치 수를 계산하는 함수를 $f_{ibonacci}(n)$이라고 합시다.

$$\begin{align*}f_{ibonacci}(5)&=f_{ibonacci}(4)+f_{ibonacci}(3)\\&=\{f_{ibonacci}(3)+f_{ibonacci}(2)\}+\{f_{ibonacci}(2)+f_{ibonacci}(1)\}\\&=f_{ibonacci}(3)+3\\&=f_{ibonacci}(2)+f_{ibonacci}(1)+3\\&=5\end{align*}$$

점화식으로 표현하면 다음과 같습니다.

$$f_{ibonacci}(1)=1,f_{ibonacci}(2)=1\\[0.5em]f_{ibonacci}(n)=f_{ibonacci}(n-1)+f_{ibonacci}(n-2)$$

이렇듯 재귀 알고리즘은 점화식으로 표할 수 있습니다.

 

점화식의 복잡도

1. 반복 대치

반복 대치는 위의 팩토리얼과 피보나치수열 예시에서 보여드린 방법입니다. 점화식의 체이닝으로 문제의 크기를 낮춰가며 경곗값까지 도달하는 방법입니다. 

위에서 보여드린 팩토리얼을 계산하는 알고리즘의 수행 시간을 $T(n)$이라 하면 $T(n)$은 점화식 $T(n)=T(n-1)+c$으로 표현될 수 있습니다.

c는 n과 $T(n-1)$을 곱하는데 소모되는 시간처럼 추가로 소비되는 시간 즉 오버헤드입니다. 이 경우 c는 n과 무관한 상수시간입니다. 위 점화식을 반복 대치해 봅시다.

$$\begin{align*}T(n)&=T(n-1)+c\\&=(T(n-2)+c)+c&=T(n-2)+2c\\&=(T(n-3)+c)+2c&=T(n-3)+3c\\&\quad\vdots\\&=T(1)+(n-1)c\\&< c+(n-1)c\\&=cn\\&=\Omicron(n)\end{align*}$$

점화식 $T(n)=T(n-1)+c$ 으로 표현되는 팩토리얼 알고리즘의 시간복잡도는 $\Omicron(n)$이 되겠네요.

 

2. 추정 후 증명

추정 후 증명은 말 그대로 복잡도를 먼저 추정하고 추정이 맞음을 귀납적으로 증명하는 방법입니다. 

점화식 $T(n)\le2T(\frac{n}{2})+n$ 으로 표현되는 $T(n)$을 추정 후 증명해 봅시다.

$$\begin{aligned}\text{경계조건}&:\quad &T(n)&\le c2\log2\text{를 만족하는 c가 존재한다.}&(1)\\[0.5em]\text{귀납적 증명}&:\quad &T(\frac{n}{2})&\le c\frac{n}{2}\log\frac{n}{2}\text{을 만족한다 가정하면,}&(2)\\[0.5em]&&T(n)&\le 2T(\frac{n}{2})+n\\[0.5em]&&\qquad&= cn\log n-cn\log2+n\\&&\qquad&= cn\log n+(1-c\log2)n&(3)\\&&\qquad&\le cn\log n&(4)\end{aligned}$$

따라서 충분히 큰 n에 대해 $T(n)\le cn\log n$인 상수 c를 잡을 수 있으므로 $T(n)=\Omicron(n\log n)$입니다.

 

3. 마스터 정리

마스터 정리는 특정 형태의 점화식에서 바로 복잡도를 계산할 수 있는 방법입니다. 

$T(n)$이 점화식 $T(n)=aT(\frac{n}{b})+n^d$ 의 형태로 표현된다면 마스터 정리를 사용할 수 있습니다. 

$$\begin{align*}&\text{when}\quad T(n)=aT(\frac{n}{b})+n^d,\\[0.5em]&T(n)= \begin{cases}\Omicron(n^{\log{_{b}a}}) &\text{if}\quad d<\log{_{b}a}\\\Theta(n^{d}\log{n}) &\text{if}\quad d=\log{_{b}a}\\\Theta(n^d) &\text{if}\quad d>\log{_{b}a}\\\end{cases}\end{align*}$$

증명은 여기서 확인하실 수 있습니다. 

추정 후 증명에서 계산했던 점화식 $T(n)\le2T(\frac{n}{2})+n$ 으로 표현되는 $T(n)$을 마스터정리를 이용하여 다시 계산해 봅시다.

$a=2,\space b=2,\space d=1$ 이므로 $d=\log{_{b}a}$ 입니다. 따라서 $T(n)=\Theta(n\log n)$입니다.