Algorithm Design - Master Theorem

---

마스터 정리

T(n) = aT(n/b) + f(n)와 같은 모양을 가진 점화식은 마스터 정리에 의해 바로 분석할 수 있다. 이번 수업시간에 다룬 내용이어서 정리를 하긴하겠으나 마스터 정리는 이전에도 정리를 했었기에 가볍게 정리하고 넘어가자.

n^(logb a) = h(n)이라 하면 아래와 같이 복잡도를 구할 수 있다.

 

 

이걸 직관적으로 표현하면 아래와 같다.

 

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

 

이때 마스터 정리를 이용할 수 있는 조건이 존재한다.

 

1. f(n)은 asymptotically positive function이어야 함
2. a>=1 and b>1이어야 함
3. the regularity condition that af(n/b) ≤cf(n) for some constant c< 1

---

Example

T(n) = 2T(n/3) + c
– a=2, b=3, h(n)=nlog32, f(n)=c

– T(n)=Θ(nlog3 2)

T(n) = 2T(n/4) + n
– a=2, b=4, h(n)=nlog4 2, f(n)=n 

– T(n)=Θ(n)

T(n) = 2T(n/2) + n
– a=2, b=2, h(n)=nlog2 2=n, f(n)=n 

– T(n)=Θ(nlogn)

 

T(n) = 2T(n/4) + c 

- a=2, b=4, h(n)=nlog2 4, f(n)=n 

- T(n) = Θ(n^2)

---

Advanced Master Theorem

위와 같이 c부분이 로그구조여서 polynomial한 비교가 불가능할때는 더 복잡한 마스터 정리가 필요하다.

위 조건에 따라 아래 문제를 풀어보자.

 

T(n)=2T(n/2)+nlogn

 

a=2, b=2, k=1, p=1 이므로 a=b^k이고 p>-1이므로 위의 2번조건에서 맨위의 식을 이용하면 아래와 같은 결과가 나온다.

 

T(n) => O(nlog2 n)

---