분할 정복(2)

Substitution Method 복습

재귀식 : T(n) = 2T(n/2) + n -> 병합정렬의 재귀식이다.
추측 : T(n) = O(n logn)

귀납에 의해 증명해야할 것 :
T(n) <= cnlog n 이 어떤 상수 c > 0에 대해 만족해야 함

먼저 basis case 의 값을 확인해보자.
이후 n < k보다 작은 경우에 맞다고 가정했을 때 n = k일 때 맞는 것을 증명해 보이면 된다.

또한 과정에서 n < k인 경우 식이 성립한다고 하면 k/2 인 경우에도 당연히 성립할 것이다.

일단 basis case는 n = 1일때는 성립하지 않으나 n >= n_0일 때 성립하면 되므로 n = 2,3,4...에 대하여 성립함을 보이면 된다.

이 경우 T(k) = 2T(k / 2) + k <= 2c(k/2)log(k/2) + k

2c(k/2)log(k/2) + k 는 ck(logk - 1) + k = ck logk + (1 - c)k
따라서 c >=1 이면 T(k) <= ck log k

Recursion Tree Method는 이미 병합정렬에서 하여 바로 Master Method로 넘어간다.

1. T(n) = aT(n/b) + f(n) 의 분할 정복에서 자주 보이는 재귀식의 형태일 때만 사용 가능

2. 다음의 경우에서만 사용 가능

(1) f(n)이 n의 (log_b a)승보다 차수가 작을 때, T(n) = Big Theta(n의 log_b a)승

(2) 차수가 같으면 T(n) = Big Theta (n의 log_b a승 * log n)

(3) f(n)의 차수가 log_b a보다 크고 n이 충분히 클 때 af(n/b) =< cf(n)인 1미만인 c가 존재하면 T(n) = Big theta (f(n))