재귀 트리

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) 이다. ...