Master Theorem

1. Introduction- [4-5] 에선 마스터 정리에 대한 공식을 알아 봤다면, 이 공식이 어떻게 나왔는지 증명을 통해서 알아보자. 2. Proof- 1) T(n)을 시그마를 이용하여 정리한다. - 2) c   - 3) c = log_b(a) 일 때, - 4) c > log_b(a) 일 때,

1. Master Theorem- 점화식으로 표현된 재귀알고리즘의 시간 복잡도를 계산할 수 있는 방법중 Master Theorem에 대해 알아보자- Master Theorem은 모든 점화식에 사용이 가능하지 않고 다음 식을 만족하는 점화식 일때만 사용이 가능하다.  - a : 분할한 부분 문제의 수, b: 입력의 크기가 줄어드는 비율 , T(n/b) :  부분문제 해결 시간, f(n) : 병합에 필요한 시간 - 이렇게 되면 T(n)의 시간 복잡도를 마스터 정리를 이용하여 구하면 다음과 같다.   - 이 식을 통해 알 수 있는 점은 병합에 걸리는 시간과 부분문제를 해결하는 시간 중에서 더 오래 걸리는 쪽의 영향을 더 많이 받아 시간복잡도가 정해진다는 것이다. 2.Exercise2.1) T(n) = 8 * ..