[Algorithm/알고리즘] Divide and Conquer, Recurrences(분할정복, 점화식)

Divide and Conquer

Divide problem into a number of subproblems

Conquer subproblems by solving them recursively

Combine solutions of the subproblem into solution for the original problem

 

 

Merge Sort

Divide: divide the sequence into two n/2 element sequences

Conquer: sort the two sequences recursively using merge sort

Combine: merge the two sorted sequences to produce the solution

n>1일 때, T(n) = 2T(n/2) + Θ(n)이다.

이것을 T(n) = 2T(n/2) + cn이라 하면,

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

= 4(2T(n/8) + cn/4) + 2cn = 8T(n/8) + 3cn

= 2^i*T(n/2^i) + icn이다. 따라서 Θ(nlgn)이다.

 

 

Recurrences

Technique 1. Repeated substitution: Expand the recurrence by substitution and then notice the pattern

Technique 2. Substitution method: Guess a bound and then use induction to prove that the guess is correct

Technique 3. Recursion trees: Convert a recurrence in a tree whose nodes represent the costs

Technique 4. Master method: Templates for different classes of recurrences

마스터 정리 (Master Theorem)

자세한 설명은 윗블로그를 참고했지만, 실질적으로 간단하게 표현하면 아래와 같다.

출처: 유튜브 주니온TV 아무거나연구소

 

단어장
decomposition 분해