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
- 해당 개념을 보고 직접 문제를 풀어보고 싶은 사람들은 다음과 같은 문제를 풀어보자.
- 풀이는 생략하고자 한다.

'CS Study > CLRS (자료구조 | 알고리즘)' 카테고리의 다른 글
| [CLRS] [4-6] Proof of the continuous master theorem (0) | 2024.09.09 |
|---|---|
| [CLRS] [4-5] The master method(마스터 정리) (0) | 2024.09.09 |
| [CLRS] [4-3] The substitution method (2) | 2024.09.06 |
| [CLRS] [4-2] Strassen’s algorithm (4) | 2024.09.06 |
| [CLRS] [4-1] Multiplying square matrices(행렬 곱) (1) | 2024.09.05 |
