4.분할정복
4.4 점화식을 풀기 위한 재귀 트리 방법
재귀 트리(recursion tree)에서는 각 노드가 재귀 호출되는 하위 문제 하나의 비용을 나타낸다. 트리의 각 레벨마다 그 비용을 합한 후 모든 레벨당 비용을 합한다.
예시: T(n) = 3T(n/4)+cn^2
T(n) 은 cn^2 + T(n/4) 3개로 이루어진다. 각 T(n/4)는 c(n/4)^2 + T(n/16) 3개로 이루어 진다. 즉 맨 위부터 각 레벨은 cn^2 1개, c(n/4)^2 3개, c(n/16)^2 9개 .. 로 반복됨을 알 수 있다. 이것이 어느정도 깊이까지 반복될까? 크기를 살펴보면 n -> n/4 -> n/16 이므로 레벨 i 에서는 n/(4^i) 임을 유추할 수 있다. 따라서 4^i = n 일때까지 반복되므로 i = log_4(n) 이라는 정수일때 까지 반복된다. i는 0단계부터 였으므로 총 횟수 log_4(n) + 1개 이다. 레벨 i = log_4(n) 이다.
위에서 말했듯 각 비용은 레벨이 0부터 cn^2, (c(n/4)^2) x 3, (c(n/16)^2) x 9, … 의 형태를 보이는데, 정리하면 레벨이 증가하면서 3배씩 증가하므로 레벨 i에서 모든 노드의 총 비용은 (3/16)^i x cn^2 이다. 마지막 레벨인 i = log_4(n)일때를 합을 구해보면:
\[(3/16)^i \cdot cn^2 = \left(\frac{3^i}{4^{2i}}\right) \cdot cn^2 , \quad i = \log_4 n \text{ 이므로} \\ \left(\frac{3^{\log_4 n}}{n^2}\right) \cdot cn^2 = c \cdot 3^{\log_4 n} \\ 3^{\log_4 n} = n^{\log_4 3} \text{ 이기 때문에} \\ c \cdot 3^{\log_4 n} = c \cdot n^{\log_4 3} \text{이다. 따라서 마지막 레벨 } i = \log_4 n \text{일때 총 비용은} \\ cn^{\log_4 3} \text{이고, } \Theta(n^{\log_4 3}) \text{이라 할 수 있다.}\]위에서 쓰인 지수와 로그 법칙은 가장 아래에 설명해놨으니 참고하길 바란다. 넘어가서, 모든 레벨에서 합을 구해보자.
\[T(n) = cn^2 + \frac{3}{16}cn^2 + (\frac{3}{16})^2cn^2+...+(\frac3{16})^{log_4n-1}cn^2+Θ(n^{log_43}) \\ T(n) = \sum^{log_4n-1}_{i=0}(\frac3{16})^icn^2 + Θ(n^{log_43}) \\ T(n) = \frac{({\frac3{16}})^{log_4n}-1}-1}cn^2 + Θ(n^{log_43})\]해를 구하기에 너무 복잡하기 때문에 무한 기하급수를 상한으로 사용한다.
\[T(n) = \sum^{log_4n-1}_{i=0}(\frac3{16})^icn^2 + Θ(n^{log_43}) < \sum^∞_{i=0}(\frac3{16})^icn^2 + Θ(n^{log_43}) \\ = \frac1{1-\frac3{16}}cn^2 + Θ(n^{log_43}) \\ = \frac{16}{13}cn^2 + Θ(n^{log_43}) \\ = O(n^2)\]오늘의 결론? 재귀 트리에서 각 레벨에서 노드들의 비용과 비용의 총합, 트리의 깊이 등을 통해 총 합을 구하여 점화식을 풀 수 있다는 것!
잘 쓰이지는 않는 지수와 로그 관계가 나왔는데 참고가 되길 바라며 추가한다.
\[c^{log_ca}=a임을 \ \ 증명해보자. \\ x=log_ca \ \ 라고 \ \ 가정하고 \ \ 이 \ \ 식의 \ \ 양변에 \ \ c의 \ \ 지수를 \ \ 취하면, \\ c^x = a이다. \ \ x=log_ca이므로 \ \ 대입하면 \\ a=c^x=c^{loc_ca} 이다. \ \ 따라서, \\ c^{log_ca}=a이다.\]이를 토대로 아래도 증명할 수 있다.
\[a^{log_cb}=b^{log_ca}이다. \ \ 왜냐하면 \\ a=c^{log_ca} 이므로 \\ a^{log_cb}=(c^{log_ca})^{log_cb} = c^{log_ca*log_cb}=c^{log_cb*log_ca} \\ =b^{log_ca} \ \ 이기 \ \ 때문이다.\]또한 T(n) 의 시그마(∑)는 공비가 3/16 인 등비수열의 합을 나타내고 있었다. 따라서 등비수열의 합 공식을 사용하였다.
\[첫째항이 \ \ a, 공비가 \ \ r인 \ \ 등비수열 \ \ a(n)의 \ \ n항까지의 \ \ 합 \ \ S(n)은 \\ S(n) = a\frac{r^n-1}{r-1}=a\frac{1-r^n}{1-r}\]