[CLRS] [4-5] The master method(마스터 정리)

1. Master Theorem

- 점화식으로 표현된 재귀알고리즘의 시간 복잡도를 계산할 수 있는 방법중 Master Theorem에 대해 알아보자

- Master Theorem은 모든 점화식에 사용이 가능하지 않고 다음 식을 만족하는 점화식 일때만 사용이 가능하다.

 

 

- a : 분할한 부분 문제의 수, b: 입력의 크기가 줄어드는 비율 , T(n/b) :  부분문제 해결 시간, f(n) : 병합에 필요한 시간

 

- 이렇게 되면 T(n)의 시간 복잡도를 마스터 정리를 이용하여 구하면 다음과 같다.

 

 

 

- 이 식을 통해 알 수 있는 점은 병합에 걸리는 시간과 부분문제를 해결하는 시간 중에서 더 오래 걸리는 쪽의 영향을 더 많이 받아 시간복잡도가 정해진다는 것이다.

 

2.Exercise

2.1) T(n) = 8 * T(n/4) + 5n^2

- c = 2

- log_b(a) = log_4(8) 

- c > log_b(a) 

- O(f(n)) = O(n^2)

 

2.2) T(n) = 8*T(n/2) + 5 * n^3

- c = 3

- log_b(a) = log_2(8) = 3

- c = log_b(a)

- O(n^3 * log_2(n))

 

2.3) T(n) = 9 * T(n/3) + 5*n

- c = 1

- log_b(a) = log_3(9) = 2

 

- c < log_b(a)

- O(n^log_b(a)) = O(n ^ 2) 

 

3. Reference

https://velog.io/@kij723/%EB%A7%88%EC%8A%A4%ED%84%B0-%EC%A0%95%EB%A6%AC-With.-%EC%8B%9C%EA%B0%84-%EB%B3%B5%EC%9E%A1%EB%8F%84

마스터 정리 (With. 시간 복잡도)

https://jjoonleo.tistory.com/28

<자료구조 알고리즘> 마스터 정리 Master theorem

 

- 다음 챕터에선 마스터 정리를 증명하고자 한다.