# 演算法 - Divide and Conquer
###### tags: `Algorithm`
## 前言
1. 遞迴公式 : 目標是求出遞迴的時間複雜度。
2. 在遞迴公式忽略的小細節:
- 合併時間。
- 底值與頂值函式。
- 邊界，都設成在$n→0$時的$T(n)為常數$。

## 一 . 取代方法
### (一) . 取代方法的應用
- 步驟 :
1. 假設可能的時間複雜度並帶入，求出 $c$。
2. 由數學歸納法求出 $n_0$。

- 例子 : $T(n)=2T(\dfrac{n}{2})+n$
1. 假設可能的時間複雜度 : $T(n)=O(nlogn)$。
2. 帶入 : $T(n)=c×nlogn$ 得 $T(n)=2c(\dfrac{n}{2})log(\dfrac{n}{2})+n$。
- 改變等號右式 : 滿足漸進符號的定義模式。
- 注意n不是n : 例如上式要帶入$\dfrac{n}{2}$。
3. 檢查是否可以使 $T(n)≦c×nlogn$。
- 已知 : $T(n)=cnlog(\dfrac{n}{2})+n$。
- 畫簡 : $T(n)=cnlogn-cnlog2+n=clogn-n(c-1)$。
- 推論 : 的$T(n)=clogn-n(c-1)$滿足假設$T(n)=O(nlogn)$即 $T(n)≦cnlogn$。
4. 得 $c$ : 在$T(n)=clogn-n(c-1)≦cnlogn$下，$1≦c$都成立。

- 數學歸納法 :