[Algorithm] Master Theorem and its application

Master Theorem, 이번 포스팅은 조금 간단하게 끝낼 것 같다. 사실 Master Theorem을 증명하려면, 더욱 더 많은 공부가 필요하나, 거기까지는 안했다. 사용법과 사용할 수 있는 조건 정도만 공부했다. 우선 Master Theorem은 Recursive function의 asymptotic function을 구하기 위해서 사용된다. asymptotic function이 뭐냐? 이전 포스팅에서 설명한 Big O, Omega, Theta와 같은 것을 말한다. Recursive function은 굳이 설명 안해도 된다고 생각한다.

우선 Master Theorem의 정의와 Master Theorem을 어떤 경우 사용할 수 있는지 그 조건을 보자.

Master Theorem 정의

Master Theorem 조건

1. For Recursive function only

2. f(n) should be polynomial function

3. Recursive function calls should have equal size

4. Value a and b should be constant

자 굳이 위의 정의를 증명을 하지 않을 계획이므로(못하므로), 몇 개 예를 들어보자. 

그리고 아래의 식은 Master Theorem이 적용되지 않는다.

T(n) = T(n/5) + T(4n/5) + n

Recursive function call T(n/5)과 T(4n/5)이 다른 사이즈다. 그래서 적용할 수 없다. Master Theorem을 실제로 적용해보면 어떻게 될까? 다음 포스팅에서 설명을 하겠지만, Sorting algorithm에서 Merge sort라고 있다. 이 sorting algorithm의 pseudo code는 아래와 같다.

Merge sort pseudo code

Recursive function은 두 개로 쪼개지기 때문에 2T(n/2)이고, 그 다음 Merge 과정에서 O(n)만큼의 더 사용된다. 따라서

T(n) = 2T(n/2) + O(n)가 된다. 이 식의 asymptotic function은 위에 Master Theorem 두번째 예제에 자세하게 유도되어있다. 다음 포스팅은 Sorting이다. 공부해보자!!