# 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.例子