[알고리즘 기초] 05 재귀 트리(Recursion Tree Method)

※ 재귀트리(Recursion Tree Method)

→ 좋은 추측식을 고안해내기 위한 직접적인 방법(치환법으로 추측이 불가능할 때)

→ 각 노드가 재귀호출되는 하위 문제 하나의 비용을 나타냄

→ 레벨당 비용의 집합을 얻기 위해 트리의 각 레벨마다 그 비용을 합한 후, 재귀의 모든 레벨에서의 총 비용을 결정하기 위해 모든 레벨당 비용을 합함

 

---

 

Example 1)

1단계 : 재귀트리를 이용하여 추측식을 구함

■ Recurrence : $T(n) = 3T(\left\lfloor n/4 \right\rfloor) + \Theta(n^2)$

 

1) 위 Recurrence식 수정

$T(n) = 3T(n/4) + cn^2$ // 내림과 올림은 그리 중요하지 않으므로 제거, $c > 0$사용

 

2) 재귀트리 사용

$n$이 정확한 4의 거듭제곱이라고 가정(정수를 만들기 위해)

 

첫 번째 확장

최종 확장

이때, 리프 노드의 비용은 총 리프 노드의 개수이므로 깊이가 $k$일 때, $T(n)$과 개수를 통해 다음과 같이 변환해준다.

 

재귀 트리의 깊이와 리프 노드의 비용

 

이제, 깊이에 따른 비용의 합이 곧 "재귀 트리의 총 비용"이므로 식을 세운다.

$i = 0, 1, 2, \cdots, \log_{4}(n-1)$에 대해 모든 노드의 총 비용(이때, i는 깊이이며, 깊이 i의 각 노드 총 비용은 $c\cdot(n/4^i)^2$이다.)

 

 

 

$\therefore$ Recurrence $T(n) = 3T(\left\lfloor n/4 \right\rfloor) + \Theta(n^2)$에 대해 $T(n)=O(n^2)$라는 추측식을 이끌어냄 

 

2단계 : 치환법을 이용하여 구한 추측식이 Recurrence식의 상한임을 검증

▶ Guess : $T(n)=O(n^2)$

▶ Prove by induction : $T(n) \le d \cdot n^2$, 어떤 상수 $d>0$에 대해 만족해야 함

▶ Inductive assumption : 

$n < k$가 참이면, (즉, $T(n) \le d\cdot n^2$)

$n=k$ 또한 참임을 만족시켜야 한다.

특히, $n=k/4$에 대해 만족해야 한다. (즉, $T(k/4) \le d\cdot (k/4)^2$ )

 

$T(k) = 3T(\left\lfloor k/4 \right\rfloor) + ck^2$, $c > 0$

 

위의 식에 부등식을 대체(치환)하면,

$T(k) \le 3d\left\lfloor k/4 \right\rfloor^2 + ck^2$

             $\le 3d(k/4)^2 + ck^2$

             $\le (3/16)dk^2 + ck^2$

             $\le (3d/16 + c)k^2$

             $\le dk^2$

 

계수d의 범위를 구하는데 참고

$\therefore d \ge 16c/13$,  $T(k) \le dk^2$

 

---

 

Example 2)

1단계 : 재귀트리를 이용하여 추측식을 구함

■ Recurrence : $T(n) = T(n/3) + T(n/2) + \Theta(n)$

 

1) 위 Recurrence식 수정

$T(n) = T(n/3) + T(n/2) + cn$ 

 

2) 재귀트리

트리 확장

위와 같이 확장했을 시 왼쪽 서브트리와 오른쪽 서브트리가 균형이 맞지 않는 것을 알 수 있다.

또한, 왼쪽 서브트리가 오른쪽 서브트리에 비해 더 빨리 $T(1)$에 가까워지는 것을 알 수 있다.

확장 시 예상되는 트리

 

각 서브 트리의 높이

 

따라서, 루트부터 리프까지 가장 긴 경로는 오른쪽 서브트리

 

각 레벨의 비용 : $cn$

트리의 높이 : $\log_{2/3}n$

점화식의 해가 많아봐야 위의 두 식을 곱한 것을 넘지 않으므로(오른쪽 트리가 왼쪽 트리보다 노드 수가 더 많기 때문)

 

$O(cn \cdot \log_{2/3}n)$ = $O(cn \cdot log_{2/3}2 \cdot log_{2}n)$ = $O(n \lg n)$

 

또한, 리프의 비용을 고려하기 위해 트리 높이가 $\log_{2/3}n$인 완전 이진 트리라면,

$\therefore$ $O(n \lg n)$

 

2단계 : 치환법을 이용하여 구한 추측식이 Recurrence식의 상한임을 검증

▶ Guess : $T(n) = O(n \lg n)$

▶ Prove by induction : $T(n) \le d \cdot n \lg n$, $d>0$에 대해 만족해야 함

▶ Inductive assumption : 

$n<k$이 참이면 (즉, $T(n) \le d \cdot n \lg n$)

$n=k$또한 만족해야 한다.

$n = k/3$, $n = 2k/3$ => 부분적으로 귀납적 가정을 만족시켜야 함

즉, $T(k/3) \le d(k/3) \lg (k/3)$, $T(2k/3) \le d(2k/3) \lg (2k/3)$

 

$T(k) = T(k/3) + T(k/2) + 2k$

 

위의 식에 부등식을 대체(치환)하면,

$T(k) \le d \cdot (k/3) \cdot \lg (k/3) + d \cdot (2k/3) \cdot \lg (2k/3) + ck$

             $\le (d(k/3) \lg k - d (k/3) \lg 3)$ + $\le (d(2k/3) \lg 2k - d (2k/3) \lg 3)$ + $ck$

             $\le dk \lg k - dk( \lg 3 - 2/3) +ck$   $(\lg2 = 1)$

 

$\therefore  d \ge c/(\lg 3 - (2/3))$, $T(k) \le dk \lg k$