---
# System prepended metadata

title: 演算法 - Divide and Conquer
tags: [Algorithm]

---

# 演算法 - 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$都成立。 
    
- 數學歸納法 : 