[중간고사] 2-(3). Divide and Conquer - Master Theorem

Master Theorem

• 재귀적인 방식으로 문제를 해결하는 경우에 자주 사용되는데, 특히 even split 알고리즘에 대한 재귀식을 다룰 때 유용
• 어떤 알고리즘의 시간 복잡도 함수 T(n)이 다음과 같은 형태일 때, 

 

다음의 1, 2, 3을 직관적으로 보면, 

1. g(n)이 무거우면 g(n)이 수행 시간을 결정한다.
2. g(n) 과 f(n)이 같은 무게이면 g(n)에 logn을 곱한 것이 수행 시간이 된다.
3. f(n)이 무거우면 f(n)이 수행 시간을 결정한다.

 

g(n)을 사용하는 이유)

하나씩 차근히 살펴보자!

Example

Master Theorem을 사용하여 주어진 재귀식을 해결해라.

T(1) = 1 and T(n) = 8T(n/2) + n^2	T(1) = 1 and T(n) = T(3n/4) + 10	T(1) = 1 and T(n) = T(n/2) + n

 

출처

https://blog.naver.com/yyj9301/221240585554

마스터 정리 Master Theorem 알고리즘 시간 복잡도 구하기