알고리즘 : 마스터 정리(Master Theorem)

어찌저찌 점화식을 구했는데, 이를 전개해서 복잡도를 알아내는 것도 쉽지만은 않다는 것을 저번 시간에 보았습니다.

하지만 우리는 언제나 방법을 찾아냅니다. 바로 "마스터 정리(Master Theorem)"입니다.

 

T(n) = aT(n/b) + f(n) 꼴의 점화식이 있다고 합시다.

물론 여기엔 조건이 붙습니다.

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.

음... 2번 빼고는 무슨 말인지 도통 모르겠네요.

 

대충 설명을 드리자면, f(n)은 positive function이어야 함, 즉 음수로 가는 함수가 아니어야 합니다.

음수로 가는 함수라면, 아예 음수가 붙은 함수(-n, -1, ...)나 음수를 거치는 함수(cosn, sinn, ...)를 그 예로 들 수 있겠죠.

 

또 a≥1 and b>1 조건에서 b>1인 이유는 b≤1인 숫자를 하나 대입해 보면 알 수 있습니다.

b에 1/2를 넣고 점화식을 전개하면 T(n) = aT(2n) + f(n)이 되죠. T(n)이 진행될수록 발산하게 됩니다.

저번 시간에 우리가 전개한 점화식은 모두 T(n)이 전개될 수록 줄어드는 형태의 점화식이었습니다.

af(n/b) ≤ cf(n)도 이와 같은 의미로, 결국 T(n)은 진행될 수록 줄어드는 형태여야 한다는 조건입니다.

 

위의 조건을 만족하는 점화식을 만나면 마스터 정리와 뒤에 설명할 Advanced Master Theorem으로 해결할 수 있습니다.

 

다음은 위 조건에 어긋나는 경우로, 마스터 정리를 적용하지 못하는 경우입니다.

• T(n) = 2ⁿT(n/2) + nⁿ

a=2ⁿ 으로, a는 1 이상의 상수여야 한다는 조건에 어긋납니다.

 

• T(n) = 0.5T(n/2) + 1/n

a=0.5로, a는 1 이상의 상수여야 한다는 조건에 어긋납니다.

 

• T(n) = 64T(n/8) - n²logn

f(n)=-n²logn 으로, f(n)은 asymptotically positive function이어야 한다는 조건에 어긋납니다.

 

• T(n) = T(n/2) + n(2-cosn)

f(n)=n(2-cosn) 으로, f(n)은 asymptotically positive function이어야 한다는 조건에 어긋납니다.

---

다시 돌아와서, T(n) = aT(n/b) + f(n) 꼴의 점화식에서 h(n) = n^logb(a) 를 정의합니다.

여기서 다음 조건에 맞게 수행시간을 결정하는 것이 마스터 정리입니다.

.... 네? 뭐라고요?

이 복잡한 영어를 직관적인 의미로 정리하면 다음과 같습니다.

T(n) = aT(n/b) + f(n) 꼴의 점화식에서 h(n) = n^logb(a) 를 정의할 때,
1. h(n)이 더 무거우면 h(n)이 수행시간을 결정한다.
2. f(n)이 더 무거우면 f(n)이 수행시간을 결정한다.
3. h(n)과 f(n)이 같은 무게이면 h(n)에 logn을 곱한 것이 수행시간이 된다.

"무겁다" 라는 표현은 "복잡도가 빨리 증가한다"로, 지난번에 나온 복잡도의 카테고리에 따라 결정됩니다.

예를 들면 O(n)보다는 O(n²)가 무겁죠.

 

아래 예제를 보며 마스터 정리를 알아보겠습니다.

 

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

a=2, b=4, f(n)=n, h(n)=n^log4(2)=n^(1/2) 을 얻을 수 있습니다.

h(n)=n^(1/2) 보다는 f(n)=n 이 더 무겁습니다.

따라서 f(n)이 수행시간을 결정하므로, T(n) = O(n)이 됩니다.

 

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

a=2, b=2, f(n)=n, h(n)=n^log2(2)=n 을 얻을 수 있습니다.

이 때, h(n)=n과 f(n)=n 이 같은 무게이므로, h(n)*logn이 수행시간이 됩니다.

따라서 T(n) = O(nlogn)이 됩니다.

 

예제를 더 살펴 보겠습니다.

• T(n) = 3T(n/2) + n²

f(n)=n², h(n)=n^log2(3) 에서, 2>log2(3) 이므로, f(n)=n²가 더 무겁습니다. 따라서 T(n) = O(n²) 입니다.

 

• T(n) = 4T(n/2) + n²

f(n)=n², h(n)=n^log2(4)=n², f(n)=h(n) 이므로, T(n) = O(n²logn) 입니다.

 

• T(n) = T(n/2) + 2ⁿ

h(n)을 굳이 구하지 않아도, f(n)=2ⁿ 보다 무거운 알고리즘은 없으므로, T(n) = 2ⁿ 입니다.

 

• T(n) = 2T(n/4) + n^0.51

f(n)=n^0.51, h(n)=n^log4(2)=n^0.5, n^0.51 > n^0.5 에서 f(n)이 더 무거우므로, T(n) = O(n^0.51) 입니다.

---

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

f(n)=nlogn, h(n)=n^log2(2)=n, 그렇다면 답은 O(nlogn) 이네요!

사실 틀렸습니다. 답은 O(nlog²n) 입니다.

마스터 정리를 썼는데, 왜 쌩뚱맞은 답이 나왔을까요?

여기에는 앞서 잠깐 말했던 "Advanced Master Theorem"이 적용되어야 합니다.

Advanced Master Theorem의 조건과 방법은 다음과 같습니다.

T(n) = aT(n/b) + f(n) 꼴의 점화식에서,
f(n)에 해당하는 부분이 nᵏlogᵖ(n)의 꼴일 때 Advanced Master Theorem을 사용하여야 한다.
이 때의 조건으로는 a≥1, b>1, k≥0, p는 실수여야 한다.

1. a > bᵏ
    h(n) = n^logb(a) 가 수행시간을 결정한다.
2. a = bᵏ
    (p > -1 일 때) n^logb(a) * logᴾ⁺¹(n)
    (p = -1 일 때) n^logb(a) * loglogn
    (p < -1 일 때) n^logb(a)
3. a < bᵏ
    (p ≥ 0 일 때) nᵏlogᵖ(n) = f(n)
    (p < 0 일 때) nᵏ

...보자마자 머리가 띵합니다.

이를 보면서 T(n) = 2T(n/2) + nlogn을 한 번 해결해 보도록 합시다.

일단 T(n) = 2T(n/2) + nlogn에서, a=2, b=2, k=1, p=1 을 얻을 수 있습니다.

그렇다면 a와 bᵏ 를 비교해야 하는 데, 2 = 2¹ 즉 a = bᵏ 이므로 2번 조건을 봐야겠죠.

이 때 p=1 > -1 이므로 T(n)은 O(n^logb(a) * logᴾ⁺¹(n))가 됩니다.

a=2, b=2, k=1, p=1을 넣어 주면 정답인 O(nlog²n) 을 얻을 수 있습니다.

 

예제를 더 살펴보고 마치겠습니다.

• T(n) = T(n/3) + nlogn

a=1, b=3, k=1, p=1에서 1 < 3¹, a < bᵏ 를 만족합니다.

3번 조건에서 p=1 ≥ 0 이므로 T(n) = O(nᵏlogᵖ(n)) 입니다.

대입을 해 주면 O(nlogn) 을 얻을 수 있습니다.

 

• T(n) = √2*T(n/2) + logn

a=√2, b=2, k=0, p=1에서 √2 > 2⁰,  a > bᵏ 를 만족합니다.
1번 조건에서 T(n) = O(n^logb(a)) = O(n^log2(√2)) = O(n^(1/2)) = O(√n) 입니다.

 

• T(n) = 3T(n/4) + nlogn

a=3, b=4, k=1, p=1 에서 3 < 4¹, a < bᵏ 를 만족합니다.3번 조건에서 T(n) = O(nᵏlogᵖ(n)) = O(nlogn) 입니다.

 

• T(n) = 6T(n/3) + n²logn

a=6, b=3, k=2, p=1 에서 6 < 3², a < bᵏ 를 만족합니다.

3번 조건에서 T(n) = O(nᵏlogᵖ(n)) = O(n²logn) 입니다.

 

• T(n) = 4T(n/2) + n/logn

a=4, b=2, k=1, p=-1 에서 4 > 2¹, a > bᵏ 를 만족합니다.

1번 조건에서 T(n) = O(n^logb(a)) = O(n²) 입니다.

 

• ※ T(n) = 2T(n/2) + n/logn

a=2, b=2, k=1, p=-1 에서 2 = 2, a = bᵏ 를 만족합니다.
2번 조건에서 p=-1 이므로 T(n) = n^logb(a) * loglogn = O(nloglogn) 인데...
책에는 "non-polynomial difference between f(n) and h(n)" 이라며 답이 없다고 나옵니다.
수업시간에 교수님도 이를 의문 삼으셔서 이 문제는 답을 말씀드리기 어렵겠네요..ㅜㅜ

 

 

<틀린 점이 있다면 지적 부탁드립니다. 감사합니다.>