[CLRS] [4-4] Recursion Tree Method(재귀 트리)

1. Introduction

- 재귀트리(Recursion Tree Method)

- 재귀 알고리즘의 Big-Theta를 알아내기 위해서 고안된 직접적인 방법론을 의미한다.

- 치환법(Substitution method)로 추측이 불가능 할 때를 의미한다.

- 예제를 통해서 한번 자세히 알아보자.

 

2. Recursion Tree Method

2.1. Example 1)

- 해당 점화식이 있다고 생각해보자.

- 위의 점화식을 다음과 같이 변형하자.

 

- 그후 다음과 같이 재귀트리를 사용하여 계산해보자(n은 4의 거듭제곱 이라고 가정)

- 이를 이용하여 전체 시간복잡도를 구해보면 다음과 같다.

 

 

2.2)Example2)

- 이번엔 계수가 다를 때의 점화식의 시간복잡도를 한번 계산해보자.

- 주어진 점화식은 다음과 같다.

 

- 이를 재귀 트리를 그리면 다음과 같다.

 

- 해당 트리를 확인해보면 왼쪽서브트리가 오른쪽 서브트리보다 상대적으로 더 빨리 T(1)에 가까워 진다는 것을 알 수 있다.

- (여기서 트리의 길이는 가장 긴 서브트리의 길이를 채택한다.)

- 간단하게 시간복잡도를 계산해보면 O(nlogn) 이라는 것을 알 수 있다.

 

3. Exercises

- 해당 개념을 보고 직접 문제를 풀어보고 싶은 사람들은 다음과 같은 문제를 풀어보자.

- 풀이는 생략하고자 한다.