分治法

🎯 什麼情境該想到我

當你「一個大問題可以拆成幾個「同樣形狀」的小問題」的時候。
★ 它是一個設計範式（不是某個演算法），而它最實用的產物是主定理——一個能秒算遞迴複雜度的工具。

⚙️ 怎麼用（三步與主定理）

三步

步驟	做什麼
Divide	把問題拆成若干個同型的子問題
Conquer	遞迴解決子問題（小到一定程度就直接解）
Combine	把子問題的解合併成原問題的解

★ 不同演算法的「重量」落在不同步驟——這是理解它們差異的關鍵：

演算法	Divide	Combine
合併排序	輕（取中點 $O (1)$ ）	重（合併 $O (n)$ ）
快速排序	重（分割 $O (n)$ ）	輕（免費）
二分搜尋	輕	免費（只遞迴一邊）

★ 主定理（Master Theorem）

對形如
$T (n) = a T (\frac{n}{b}) + f (n), a \geq 1, b > 1$

令 $n^{l o g_{b} a}$ 為「遞迴的葉子總工作量」，與 $f (n)$ （每層合併的工作量）比大小：

Case	條件	結果	誰主導
1	$f (n) = O (n^{l o g_{b} a - ε})$	$T (n) = Θ (n^{l o g_{b} a})$	葉子（遞迴底層）
2	$f (n) = Θ (n^{l o g_{b} a})$	$T (n) = Θ (n^{l o g_{b} a} lo g n)$	每層一樣重
3	$f (n) = Ω (n^{l o g_{b} a + ε})$ ＋正則條件 $a f (n / b) \leq c f (n)$	$T (n) = Θ (f (n))$	根（最上層的合併）

直覺：畫出遞迴樹，比較「最上面那一層的合併成本」與「最底層所有葉子的成本」，誰大誰主導；一樣大就多一個 $lo g n$ 。

套用範例

遞迴式	$a$	$b$	$n^{l o g_{b} a}$	$f (n)$	Case	結果
合併排序 $2 T (n /2) + Θ (n)$	2	2	$n$	$Θ (n)$	2	$Θ (n lo g n)$
二分搜尋 $T (n /2) + Θ (1)$	1	2	$n^{0} = 1$	$Θ (1)$	2	$Θ (lo g n)$
二元樹走訪 $2 T (n /2) + Θ (1)$	2	2	$n$	$Θ (1)$	1	$Θ (n)$
Karatsuba 乘法 $3 T (n /2) + Θ (n)$	3	2	$n^{1.585}$	$Θ (n)$	1	$Θ (n^{1.585})$
Strassen 矩陣乘 $7 T (n /2) + Θ (n^{2})$	7	2	$n^{2.807}$	$Θ (n^{2})$	1	$Θ (n^{2.807})$
某些切割問題 $2 T (n /2) + Θ (n^{2})$	2	2	$n$	$Θ (n^{2})$	3	$Θ (n^{2})$

★ Karatsuba 與 Strassen 是分治最漂亮的成果：
它們的價值不在「把問題拆小」（那誰都會），而在用更多的加減法換掉一次乘法／矩陣乘，
把 $a$ 從 4 降到 3、從 8 降到 7 —— $a$ 少一，指數就降下來。
分治的威力來自「減少子問題的數量」，不是「拆得更細」。

★ 主定理不適用時

$f (n)$ 落在兩個 case 之間的「縫隙」（例如 $T (n) = 2 T (n /2) + n lo g n$ ）
子問題大小不等（ $T (n) = T (n /3) + T (2 n /3) + n$ ）
→ 改用遞迴樹或代入法證明

★ 分治 vs 動態規劃（最重要的界線）

	分治	動態規劃
子問題	互相獨立、不重疊	★ 重疊（同一個子問題被算很多次）
做法	直接遞迴	記憶化 or 自底向上表格
例子	合併排序、快排、二分搜尋	費氏數列、背包、最長公共子序列

費氏數列用純分治：
fib(5) → fib(4) + fib(3)
         fib(3)+fib(2)  fib(2)+fib(1)
         ★ fib(3) 被算了兩次，fib(2) 三次⋯ → O(φⁿ) 指數爆炸

加上記憶化 → O(n)

★ 判準：畫出遞迴樹，看有沒有重複的節點。
有重複 → 用 DP；沒重複 → 分治就夠了。

還有一個實務價值：平行化

子問題獨立 → 可以並行。

func parallelMergeSort(a []int, depth int) {
    if len(a) < 1000 || depth <= 0 {   // ★ 太小就別開 goroutine，開銷大於收益
        sequentialSort(a)
        return
    }
    mid := len(a) / 2
    var wg sync.WaitGroup
    wg.Add(1)
    go func() { defer wg.Done(); parallelMergeSort(a[:mid], depth-1) }()
    parallelMergeSort(a[mid:], depth-1)   // ★ 當前 goroutine 做另一半，不要開兩個
    wg.Wait()
    merge(a, mid)
}

★ 限制遞迴深度，否則會開出成千上萬個 goroutine——排程開銷會遠大於平行的收益。

🧪 我實際套用的紀錄

（待填）

⚠️ 注意 / 什麼時候不適用

★ 子問題重疊就不要用分治，會指數爆炸 → 改動態規劃。
遞迴有開銷。小問題要切換成迭代或簡單演算法（所有排序在小分段切插入排序就是這個道理）。
堆疊深度。不平衡的分治（如退化的快排）會爆堆疊。
主定理不是萬用，有縫隙情況。
平行化要限制深度，否則 goroutine/thread 的開銷吃掉收益。
分治不保證更快。 $a$ 、 $b$ 、 $f (n)$ 的組合可能讓它比直接做還慢——先算主定理再實作。

🔗 相關工具

合併排序、快速排序、二分搜尋 —— 三個代表性範例
動態規劃 —— 子問題重疊時的替代範式
順序統計量與中位數 —— 「只遞迴一邊」的變體
工具-遞迴式與主定理 —— 更完整的遞迴式求解方法
工具-時間複雜度分析、工具-演算法設計策略 —— 決策層
演算法導論

Quartz 5

Explorer

分治法