쉽게 배우는 알고리즘 2장. 점화식과 점근적 복잡도 분석 http://academy.hanb.co.kr

2장. 점화식과 점근적 복잡도 분석 사실을 많이 아는 것보다는 이론적 틀이 중요하고, 기억력보다는 생각하는 법이 더 중요하다. - 제임스 왓슨

학습목표 재귀 알고리즘과 점화식의 관계를 이해한다. 점화식의 점근적 분석을 이해한다.

점화식의 이해 점화식 예 어떤 함수를 자신보다 더 작은 변수에 대한 함수와의 관계로 표현한 것 an = an-1 + 2 f(n) = n f(n−1) f(n) = f(n−1) + f(n−2) f(n) = f(n/2) + n

Mergesort의 수행시간 수행시간의 점화식: T(n) = 2T(n/2) + 오버헤드 mergeSort(A[ ], p, r) {         if (p < r) then {                 q ← (p+q)/2;   -----------------------  ①   ▷ p, q의 중간 지점 계산                 mergeSort(A, p, q);  ----------------  ②   ▷ 전반부 정렬                 mergeSort(A, q+1, r); --------------  ③   ▷ 후반부 정렬                 merge(A, p, q, r);  ------------------  ④   ▷ 병합         } } merge(A[ ], p, q, r)         정렬되어 있는 두 배열 A[p ... q]와 A[q+1 ... r]을 합하여         정렬된 하나의 배열 A[p ... r]을 만든다. 수행시간의 점화식: T(n) = 2T(n/2) + 오버헤드 크기가 n인 병합정렬 시간은 크기가 n/2인 병합정렬을 2번 하고 나머지 오버헤드를 더한 시간이다

점화식의 점근적 분석 방법 반복대치 추정후 증명 마스터 정리 더 작은 문제에 대한 함수로 반복해서 대치해 나가는 해법 결론을 추정하고 수학적 귀납법으로 이용하여 증명하는 방법 마스터 정리 형식에 맞는 점화식의 복잡도를 바로 알 수 있다

반복대치 T(n) = T(n−1) + n T(1) = 1 T(n) = T(n−1) + n = (T(n−2) + (n−1)) + n = (T(n−3) + (n−2)) + (n−1) + n … = T(1) + 2 + 3 + … + n = 1 + 2 + … + n = n(n+1)/2 = Θ(n 2)

반복대치 T(n) = 2T(n/2) + n T(1) = 1 T(n) = 2T(n/2) + n = 2(2T(n/22) + n/2) + n = 22T(n/22) + 2n = 22(2T(n/23) + n/22) + 2n = 23T(n/23) + 3n … = 2kT(n/2k) + kn = n + n log n = Θ(n log n) ~9/10/2007

추정후 증명Guess&Verification T(n) = 2T(n/2) + n 추정: T(n) = O(n log n), 즉 T(n) ≤ cn log n <증명> T(n) = 2T(n/2) + n ≤ 2c(n/2) log(n/2) + n = cn logn − cn log2 + n = cn logn + (−c log2 + 1)n ≤ cn log n 이를 만족하는 c가 존재한다

추정후 증명 T(n) = 2T(n/2) + 1 추정: T(n) = O(n ), 즉 T(n) ≤ cn <증명> 귀납적 가정 이용 더 이상 진행 불가!

추정후 증명 추정: T(n) ≤ cn -2 <증명> T(n) = 2T(n/2) + 1 귀납적 가정 이용

마스터 정리Master Theorem T(n) = aT(n/b) + f (n)와 같은 모양을 가진 점화식은 마스터 정리에 의해 바로 결과를 알 수 있다 nlogb a = h(n)이라 하자 ① 어떤 양의 상수 ε에 대하여 f(n)/h(n) = O(1/nε)이면, T(n) = Θ(h(n))이다. ② 어떤 양의 상수 ε에 대하여 f(n)/h(n) = Ω(1/nε)이고, 어떤 상수 c(< 1)와 충분히 큰 모든 n에 대해 af(n/b) ≤ cf(n)이면 T(n) = Θ(f(n))이다. ③ f(n)/h(n) = Θ(1)이면 T(n) = Θ(h(n) log n)이다.

마스터 정리의 직관적 의미 ① h(n)이 더 무거우면 h(n)이 수행시간을 결정한다. ② f(n)이 더 무거우면 f(n)이 수행시간을 결정한다. ③ h(n)과 f(n)이 같은 무게이면 h(n)에 log n을 곱한 것이 수행시간이 된다.

마스터 정리의 적용 예 T(n) = 2T(n/3) + c T(n) = 2T(n/4) + n T(n) = 2T(n/2) + n a=2, b=3, h(n) = nlog3 2, f(n) = c T(n) = Θ(nlog3 2) T(n) = 2T(n/4) + n a=2, b=4, h(n) = nlog4 2, f(n) = n T(n) = Θ(n) T(n) = 2T(n/2) + n a=2, b=2, h(n) = nlog2 2 = n, f(n) = n T(n) = Θ(n log n)

Thank you