分而治之 是演算法設計的基石策略：**將大問題分解為相似的小問題、遞歸求解、合併結果**。本文系統闡述核心框架、遞歸複雜度分析 (Master Theorem)、五大經典應用 (偽幣、最小最大、矩陣乘法、殘缺棋盤、最近點對)、非遞歸實作技巧與下界證明。
k 個規模較小的子問題 (通常 k=2)。遞歸關係**：T(n) = a T(n/b) + f(n)，其中 a 子問題數、n/b 子問題規模、f(n) 分解合併成本。
n 枚硬幣中 1 枚較輕，天平比較，找出偽幣。T(n) = T(n/3) + 1 → T(n) = ⌈log₃ n⌉。n=16：分治 3 次 (3等分) vs 線性 8 次 (兩兩比較)。n 元素，找最小值與最大值。T(n) = 2T(n/2) + 2, T(2)=1 → T(n) = 3n/2 - 2 (n 為 2 的冪)。3n/2 - 2 次比較，無遞歸開銷。⌈3n/2⌉ - 2 次比較 (決策樹葉數 ≥ 排列組合數)。分治達成下界 → **最優**。C[i][j] = Σ A[i][k]B[k][j] → n³ 乘法、n²(n-1) 加法。n/2 子矩陣 → 8 次遞歸乘法 + 4 次矩陣加法 → T(n) = 8T(n/2) + O(n²) → O(n³) (無提升)。T(n) = 7T(n/2) + O(n²) → O(n^{log₂7}) ≈ O(n^{2.81})。O(n^{2.376})、近年 O(n^{2.37286})，但常數極大僅理論意義。2^k × 2^k 棋盤缺 1 格，用 L 型骨牌 (3 格) 完全覆蓋。2^{k-1} 子棋盤 → 在中心放 1 個 L 型骨牌覆蓋 3 個完整子棋盤的角落 → 每子棋盤恰好缺 1 格 → 遞歸覆蓋。(4^k - 1)/3，遞歸深度 k，時間 O(4^k) (輸出敏感最優)。T(n) = 2T(n/2) + O(n) → O(n log n)，達成下界 Ω(n log n) (代數決策樹模型)。遞歸雖優雅但有**函數呼叫開銷**、**堆疊溢位風險**。許多分治演算法可轉為迭代：
判斷準則**：遞歸深度 O(log n) 通常安全；O(n) 深度 (如快速排序最壞情況) 必須改迭代或隨機化。
T(n) = aT(n/b) + f(n))| 情況 | 條件 | 解 | 範例 |
|---|---|---|---|
| 1 | f(n) = O(n^{log_b a - ε}) | Θ(n^{log_b a}) | Strassen: a=7,b=2,f=n² → n^{log₂7} |
| 2 | f(n) = Θ(n^{log_b a} log^k n) | Θ(n^{log_b a} log^{k+1} n) | 歸併排序: a=2,b=2,f=n → n log n |
| 3 | f(n) = Ω(n^{log_b a + ε}) 且 af(n/b) ≤ cf(n) | Θ(f(n)) | 快速排序平均: f(n)=n → Θ(n log n) |
結語**：分而治之以「化整為零、遞歸求解、合併結果」的優雅框架，解決了從排序、搜尋、矩陣運算到計算幾何的核心問題。掌握遞歸式分析、Master Theorem、非遞歸轉換與下界證明，是演算法工程師從「會用」進階到「會設計、會優化、會證明」的關鍵門檻。
