Analysis of Algorithms | Solving Recurrences

읽기 전

• 해당 게시물은 작성자가 학습한 내용을 정리 및 요약 목적으로 작성되었으므로 오역 및 오개념이 있을 수 있습니다. 바로잡기 위한 의견을 제시해주시면 매우 감사하겠습니다.

알고리즘 문제를 해결함에 있어 반복문은 매우 중요한 역할을 한다. 그러나 2번까지는 nest된 형태로 동일 기능을 수행하도록 코드를 작성할 순 있겠지만, 그 이상이 되면 재귀함수를 호출하는 것이 도움이 될 것이다.

물론 필자도 처음 프로그래밍을 공부할 때 재귀함수를 사용할 시에는 스택과 메모리 측면에서 위험할 수 있다는 조언을 들었지만 그 위험을 막기 위해 정확하게 input을 정하고 값의 변화를 구체적으로 파악하여 종료시점을 오류가 발생하지 않도록 정할 수 있도록 연습해야 할 것이다. 그 조언을 듣고 재귀함수 공포증이 생겨 문제를 풀 때 엄청난 곤혹을 치르고 있다,

이번 게시글에서는 재귀를 해결하는 데 주로 소개되는 3가지 방법을 다루고자 한다.

치환법(Substitution Method)

해답에 대해 가정을 두고 수학적으로 그 가정이 성립하는지 판별하는 방법이다. 어떤 문제를 해결하는 데 걸리는 시간이 $T(n)=2T(\cfrac{n}{2})+n$라고 하자.($T(n)$=사이즈가 n인 문제를 해결하는 데 걸리는 시간) 1번 연산에 n시간이 소요되고 매개번수가 2씩 나뉘므로 $log_{2}n$회 수행하여 총 시간은 $nlog_{2}n$이 되어 시간복잡도는 $O(nlog\ n)$이라 생각할 수 있다. 그렇다면 $T(n)\le cnlog\ n$이 성립하면 가정도 성립한다 볼 수 있다.

$T(n)=2T(\cfrac{n}{2})+n \le 2\cdot\cfrac{cn}{2}log(\cfrac{n}{2})+n$

$=cnlog\ n - cnlog\ 2+n$

$=cnlog\ n -n(clog\ 2-1)$

즉 n이 클 수록 $T(n)$은 점근적으로 $cnlog\ n$에 접근함을 확인할 수 있다.

재귀 트리 방법(Recurrence Tree Method)

트리의 각 레벨 당 어느 정도의 시간이 소요되었는지 계산하여 재귀 트리의 모든 레벨에 대해 소요된 시간을 더하는 방법이다. 어떤 문제를 해결하는 재귀함수의 소요시간을 $T(n)=T(\cfrac{n}{4})+T(\cfrac{n}{2})+cn^2$이라 하자. 이 함수의 관계를 트리 형태로 표현하면 다음과 같다.

이후 자식 노드에 대해서도 풀어서 표현하면 다음과 같다.

이런 식으로 계속 트리가 뻗어나가게 되며, 각 트리 레벨 당 발생된 노드들의 합을 구하면 $cn^2(1+\cfrac{5}{16}+\cfrac{25}{256}+\cdots)$가 됨을 확인할 수 있다. 즉, $cn^2$에 대해 정리하면 초항이 1이고 공차가 $\cfrac{5}{16}$인 등비수열이다. 등비수열의 합공식을 사용하여 계산하면 $\cfrac{16}{11}cn^2$이 되고 결국 함수의 시간복잡도는 $O(n^2)$임을 알 수 있다.

마스터 방법(Master Method)

알고리즘의 수행시간을 점근적으로 계산하여 간단하게 구하는 방식이라고 소개되어 있다. 다만, 수행시간의 형태가 $T(n)=aT(\cfrac{n}{b})+f(n)$, $(a\ge1, b>1)$의 형태를 띠거나 해당 식으로 변환이 가능하고 재귀부가 아닌 $f(n)$이 다항식 형태이거나 복잡도를 명확하게 표현할 수 있는 경우에만 적용 가능하다. 모든 경우에 사용할 수 있는 방법은 아니다. 좀 더 사용범위를 확대한 Advanced master method가 있다고는 하는데 추후에 기회가 되면 다루겠다.

문제에서 제시된 재귀함수는 아래와 같이 트리구조를 가지고 전개된다.

이 방법은 3가지 기준을 가지고 시간복잡도를 계산한다. 왜 다음과 같이 되는지 정리된 글이 없어 최대한 필자가 이해한 대로 작성하였다.

1. 만약 $f(n)=\Theta(n^c)$일 때, $c<log_{b}a$이면 $T(n)=\Theta(n^{log_{b}a})$이다.

   전체 수행시간은 $n^c(1+\cfrac{a}{b^c}+\cfrac{a^2}{b^{2c}}+\cdots+\cfrac{a^{k-1}}{b^{(k-1)c}})$형태이다. 조건에 따라 공차인 $\cfrac{a}{b^c}$가 1보다 크므로 레벨이 높아질 수록 해당 레벨의 수행시간 노드를 합한 값이 커진다. 결국 수행시간을 모두 더한 값은 가장 아래 단계 레벨 노드의 수행시간의 합으로 수렴한다. 마지막 레벨의 노드 개수는 $a^{log_{b} n}=n^{log_{b} a}$이고 각 노드별 수행시간은 $T(1)$이다. 이 값은 $n^{log_{b}a}\cdot T(1)$으로 표현할 수 있으며 이에 따라 시간복잡도는 $\Theta(n^{log_{b}a})$가 된다.

2. 만약 $f(n)=\Theta(n^c)$일 때, $c=log_{b}a$이면 $T(n)=\Theta(n^c log\ n)$이다.

   조건에 따라 공차는 1이 되어 각 레벨 노드 별 수행시간의 합은 $n^c$으로 일정하다. 마지막 레벨의 깊이는 $log_{a} n$이므로 전체 수행시간은 $n^c\cdot log_{b}n$이 된다. 즉, $n^clog\ n$의 범위로 종속할 수 있으므로 시간복잡도는 $\Theta(n^clog\ n)$이다.

3. 만약 $f(n)=\Theta(n^c)$일 때, $c>log_{b} a$이면 $T(n)=\Theta(f(n))$이다.

   마지막 항이 0에 수렴한다 생각하여 등비급수의 합공식을 적용하면 $\cfrac{1}{1-r}n^c$, $(r=\cfrac{a}{b^c})$가 된다. 즉, $n^c$의 범위에 종속되므로 시간복잡도는 $\Theta(f(n))$이다.

마지막 마스터 방법은 왜 조건에 따라 저렇게 분기가 나뉘는 지 이해하는 데 시간이 좀 걸렸다. 다른 이들은 너무 당연하게 이해가 되나 보다....

참고자료

1. Analysis of Algorithm | Set 4 (Solving Recurrences)