Divide and Conquer의 재귀문제를 공식으로 풀기

얼마나 봤다고 벌써 친숙해진 divide and conquer... 그냥 잘게 쪼개고, 재귀로 하위 문제를 정복하고, 하위 문제들을 합치는 어려울 것 없는 방식이지만... 재귀다 보니 시간복잡도를 구하기가 좀 까다로웠다. 하지만 그것도 이 시간이 마지막(이 되길..), 오늘은 지금까지 배웠던 것을 바탕으로 한 공식을 알아볼 것이다.

우선 지난번에 배웠던 substitution 방법과 recursion-tree 방법을 짧게 알아보고, 다른 사람들이 계속 이런 방식을 반복하다보니 만들어낸 정형화된 공식을 알아보자.

 

 

일단 지금까지 써왔던 재귀 방법이다.

1. 우선 recursion-tree 방법을 사용해서 문제를 추측하자

(recursion-tree를 그리고, 각 레벨의 cost를 계산한 다음, level을 계산해서, 모든 레벨의 cost를 합한다.)

여기선 level = log n 에 모든 레벨의 코스트 cn(코스트 c가 n개)들을 전부 합하여 (결국 곱해서) n log n의 식을 얻었다.

 

 

2. 수학적인 추론으로 추측이 맞음을 증명한다.

추측한 것을 식에 그대로 대입(치환)하여 증명이 맞나 확인한다.

 

 

 

---

 

 

 

지금까지 배운 방법은 생각보다 시간이 오래 걸리고(tree 그리느라..) 일단 무엇보다 어렵다.(나만어렵나?)

이제 궁극의 방법을 소개한다.

일반적으로 T(n)의 식이 주어질 때, 위의 식에서 a는 우리가 나눠서 분석할 (divide단계) 하위문제의 개수를 의미하고 b는 문제가 점점 줄어드는 비율을 의미한다. f(n)은 fixed cost로 우리가 사용할 divide and combining의 최종 비용을 의미한다. 그래서 top level에 위치한다. 

자꾸 헷갈려서 적는 last level에서의 cost 구하는 법.

왜 n^(log b a)가 나왔는지 헷갈린다. 일단 log b n은 우리가 구하려는 레벨 k 가 (n = b^k)로 구해지기 때문이라 쉽다.

last level의 총 cost는 각 비용 세타(1)에 총 개수 a^k 를 곱해주면 되는데 여기서 k가 log b n이므로 총 비용은 근사하여 a^(log b n)인데 여기서 log공식으로 조작하면 n^(log b a)가 된다.

 

 

뭐 어려울건 없다. 이것은 그냥 정형화된 공식으로, a b f(n)의 값들을 비교하는 데에서 시작한다.

case 1 : 만약 f(n)이 n^(logb a) 보다 작거나 같으면 T(n)은 n^(logb a)이다.

case 2 : 만약 f(n)이 n^(logb a) 와 같으면 T(n)은 n^(logb a) * log n 이다.

case 3 : 만약 f(n)이 n^(logb a) 보다 크거나 같으면 T(n)은 f(n)이다.

0보다 큰 상수 입실론은 여기에 한글로 안적었는데, 근사치를 구하는 것이므로 꼭 필요하니까 빼먹지 말자..

 

 

예를들어 T(n) = 2T(n/2) + n 인 경우  a = 2, b = 2, f(n) = n 이므로 f(n)과 비교하여 case2를 적용해보면
세타 n log n으로 근사된다.

T(n) = T(n/2) + n^2 인 경우 a = 1, b = 2, f(n) = n^2 이므로 f(n)과 비교하여 case3을 적용해보면
T(n) = 세타(f(n))이므로 n^2으로 근사된다.

T(n) = 4T(n/2) + n 인 경우 a = 4, b = 2, f(n) = n 이므로  f(n)과 비교하여 case1을 적용해보면
T(n) = n^(log2 4) 이므로 n^2로 근사된다.

 

일단 n의 로그승과 f(n) 값을 비교하는 데에서 시작하는 것이다. 셋 다 등호 표시가 들어가므로 아주 작은 값 입실론을 고려해서 모두 성립하는 case를 찾아서 적용하자.