알고리즘 분석 | The Master Method | 마스터 정리

이전 포스팅

알고리즘 분석 | 힙 정렬 | 분할 정복 Divide & Conquer | 병합 정렬 Merge sort

 

The Master Method란

The Master Method(마스터 정리)는 점화식(recurrence equation)을 해결하기 위한 일반적인 방법 중 하나로, 분할 정복(divide and conquer) 알고리즘에서 주로 사용됩니다.

마스터 정리는 점화식이 특정한 형태일 때, 점화식의 해를 구할 수 있는 일반적인 방법을 제공합니다. 마스터 정리는 다음과 같은 형태의 점화식을 해결할 수 있습니다.

\(T(n) = aT(n/b) + f(n)\)

여기서 \(a\)는 재귀 호출의 개수, \(b\)는 입력의 크기를 나누는 비율, \(f(n)\)은 재귀 호출이 아닌 부분에서 수행되는 연산입니다. 이러한 점화식의 해를 구하기 위해, 다음과 같은 3가지 조건을 검사합니다.

Case 1: \(f(n) = O(n^{log_b(a)-ε})\)인 경우, \(T(n) = Θ(n^{log_b(a)})\)입니다.
Case 2: \(f(n) = Θ(n^{log_b(a)})\)인 경우, \(T(n) = Θ(n^{log_b(a)} * log(n))\)입니다.
Case 3: \(f(n) = Ω(n^{log_b(a)+ε})\)이고, \(a * f(n/b) ≤ c * f(n)인 경우, T(n) = Θ(f(n))\)입니다.

여기서 \(ε\)는 임의의 양수이고, \(c\)는 \(1\)보다 큰 상수입니다. 각각의 조건에서, \(a, b, f(n)\)을 알고 있다면, 점화식의 해를 빠르게 구할 수 있습니다.

마스터 정리는 분할 정복 알고리즘에서 자주 사용되며, 알고리즘의 실행 시간을 예측하는 데에 유용합니다.

---

The master method 문제 풀이

 

Case 1 : \(T(n) = 4T(n/2) + n\)

Fig .1 문제 1

풀이

\(a = 4 , b = 2 , f(n) = n\).

이와같은 케이스는, \( n^{log_b(a)} = n^{log_2(4)} = n^2\).

그러므로, 우리는 Case 1에서 , for \(f(n)\) is \(O(n^{2-\epsilon})\) for \(\epsilon = 1\).

고로 The Master method에 의해서  \(T(n) 는 \varTheta(n^2)\) 입니다

---

 

Case 2 : \(T(n) = T(2n/3) + 1\)

Fig. 2. 문제 2

풀이

\(a = 1, b = 3/2, f(n) = 1\).

이와같은 케이스는 \(n^{log_3/2(1)} = n^0 = 1\).

Case 2 적용하여, \(f(n) = \varTheta(n^{log_b(a)})  = \varTheta(1)\)

그러므로 \(T(n) = \varTheta(lg n)\)

---

Case 3 : \(T(n) = T(n/3) + 3\)

Fig. 3. 문제 3

풀이

\(a = 1, b = 3, f(n) = n\).

이와 같은 케이스는, \(n^{log_3(1)} = n^0 = 1\).

Case 3을 적용하면, \(f(n) = \varOmega(n^{0+\epsilon})\), for \(\epsilon = 1\)

그리고 \(af(n/b) \le cf(n)\), for \(c < 1\), and  \(af(n/b) = n/3 = (1/3)f(n)\).

그러므로 the master method에 의해서 \(T(n) = \varTheta(n)\).

---

 

Tip !

핵심은 \(f(n)\)의 값과 \(n^{log_b(a)} \)값을 비교했을때, 어떤 케이스를 적용할 수 있을 지 보는 것 입니다!!

\(f(n) = n\) 일때, \(n^{log_b(a)} = n^2\) 이라면 Case 1,

\(f(n) = n\) 일때, \(n^{log_b(a)} = n\) 이라면 Case 2,

\(f(n) = n\) 일때, \(n^{log_b(a)} = 1 = n^0\)이고  \(af(n/b) \le cf(n)\), for \(c < 1\) 라면 Case 3를 적용하는 것 입니다

 

---