Divide and Conquer

1.Introduction

• 將問題先切分成小問題後再解決, 再將結果合併求出原始問題的答案

2.作法

1. 分解：將原問題分解為若干個規模較小，相對獨立，與原問題形式相同的子問題。

2. 解決：若子問題規模較小且易於解決時，則直接解。否則，遞歸地解決各子問題。

3. 合併：將各子問題的解合併為原問題的解。

3.Recurrence

• recurrence: 表示為問題大小為size n的整體的running time與divide and conquer後的running time

• D(n)是將問題分為子問題所需的時間, C(n)是將子問題的解合併起來所需的時間, a是子問題的數量, 1/b是子問題與原問題的比例, 則:

T(n) = 
Θ(1)       if n ≤ c
aT(n/b) + D(n) + C(n)    otherwise

4.例子