# Ch4：Divide-and-Conquer
分治法是透過將原問題分解成幾個規模較小、形式相同或相似的子問題，遞迴地解決各子問題，最後再將這些子問題的解合併，得到原問題的解。

## 基本步驟
所有分治法皆可拆分為三個步驟：
1. **Divide（分割）**：把大規模問題分割成好幾個小問題
2. **Conquer（征服）**：對每個小問題**遞迴**求解
3. **Combine（合併）**：整合小問題的答案，形成原問題的答案

## 範例：矩陣乘法
$n \times n$ 矩陣乘法可以透過分治法來加快執行時間
- 問題：$A \times B = C$
- 先把 $n \times n$ 矩陣分割成 4 個 $\frac{n}{2} \times \frac{n}{2}$ 矩陣
- $A = \left(
\begin{array}{ccc}
A_{11} & A_{12} \\
A_{21} & A_{22}
\end{array}
\right), B = \left(
\begin{array}{ccc}
B_{11} & B_{12} \\
B_{21} & B_{22}
\end{array}
\right)$
- \begin{align*}C=A \times B &= \left(
\begin{array}{ccc}
A_{11} & A_{12} \\
A_{21} & A_{22}
\end{array}
\right)\times \left(
\begin{array}{ccc}
B_{11} & B_{12} \\
B_{21} & B_{22}
\end{array}
\right) \\ &= \left(
\begin{array}{ccc}
A_{11} \times B_{11} + A_{12} \times B_{21} & A_{11} \times B_{12} + A_{12} \times B_{22} \\
A_{21} \times B_{11} + A_{22} \times B_{21} & A_{21} \times B_{12} + A_{22} \times B_{22}
\end{array}
\right)
\end{align*}
- 我們必須求出這八個小乘法然後加起來，就可以得到 C 的答案
- **Presudo code**：
- 遞迴式：$T(n) = 8T(n/2) + \Theta (1)$

## 遞迴式轉一般式的解法
### 替換法（Substitution Method）：
- 先猜測遞迴式的解
- 利用 **數學歸納法** 或 直接替換來證明

### 遞迴樹法（Recursion-Tree Methods）：
- 將遞迴關係化成一顆樹，每一層代表一次分割子問題
- 步驟：
- 範例：$T(n) = 3T(n/4) + \Theta(n^2)$
- 先畫出第一層：
- 然後畫出第二層：
- 第三層：
- $T(n/4) = 3T(n/16) + \Theta((n/4)^2)$
- 依此類推，然後每一層加起來找規律：

### 主定理（Master Theorem）
:::warning
主定理**並非萬用**，必須遞迴式符合格式才可以用
:::
- 當遞迴式為 $T(n) = aT(n/b) + f(n)$ 時：
- **Case 1**：當 $\cfrac{f(n)}{n^{\log_ba}} \rightarrow 0$
- 即 $f(n) < n^{\log_ba}$
- $T(n) = \Theta(n^{\log_ba})$
- **Case 2**：當 $\cfrac{f(n)}{n^{\log_ba}} = constant$
- 即 $f(n) = n^{\log_ba}$
- $T(n) = \Theta(f(n)\lg n)$
- **Case 3**：當 $\cfrac{f(n)}{n^{\log_ba}} \rightarrow \infty$
- 滿足 $\mathrm{for\ \epsilon > 0},\ f(n) = \Omega(n^{\log_ba-\epsilon})$
- **正規化條件**：
- 滿足 $af(n/b)\le cf(n)$
- 即 $f(n)$ 為**多項式函數**
- 即 $f(n) > n^{\log_ba}$
- $T(n) = \Theta(f(n))$