漫談算法（四）：分治算法遞歸式求解三大法——數學歸納法、遞歸樹、主定理

作者：劉子韜

分治算法定義

基於多分支遞歸的算法設計範式：將問題遞歸分解為同類子問題，直到足夠簡單直接求解，再合併子問題解得到原問題解。

核心兩步走

1. 建立遞歸式：描述問題規模 n 與子問題規模關係
2. 求解遞歸式：得到時間複雜度閉式解

例：T(n) = 4T(n/2) + n

三大求解方法

方法一：數學歸納法

核心：猜測答案形式 → 數學歸納證明

例題：T(n) = T(n/2) + T(n/4) + T(n/8) + n

猜測：T(n) = Θ(n)

證明 Ω(n)：T(n) > n 顯然成立

證明 O(n)：假設 T(n) ≤ cn

T(n) ≤ c·n/2 + c·n/4 + c·n/8 + n = (7c/8 + 1)n
令 (7c/8 + 1)n ≤ cn → c ≥ 8 成立

∴ T(n) = Θ(n)

猜測直覺來源：遞歸樹觀察

每層總代價遞減，頂層 n 主導 → 猜測 Θ(n)

兩個猜測小技巧

1. T(n) = aT(n/b + d) + f(n) 中，n 足夠大時 d 可忽略
2. 歸納假設可加常數項：T(n) ≤ cn - d，消除常數干擾

方法二：遞歸樹法

核心：畫樹 → 按層求和 → 幾何級數求和

通用遞歸式：T(n) = aT(n/b) + nᵏ

樹高 h = log_bn

第 i 層：aⁱ 個節點，每節點代價 (n/bⁱ)ᵏ = nᵏ/bⁱᵏ

第 i 層總代價：aⁱ · nᵏ/bⁱᵏ = nᵏ · (a/bᵏ)ⁱ

總代價：Σ_i=0^h-1 nᵏ(a/bᵏ)ⁱ + 葉子代價

不平衡遞歸樹高度計算

T(n) = T(n/3) + T(2n/3) + O(n)

最長分支決定高度：n → (2/3)n → (2/3)²n → ... → 1

高度 k 滿足 (2/3)ᵏn = 1 → k = log_3/2n

方法三：主定理

適用形式：T(n) = aT(n/b) + f(n)，a ≥ 1, b > 1

三大情況

1. f(n) = O(n^{log_ba - ε}) → T(n) = Θ(n^log_ba)
2. f(n) = Θ(n^log_ba log^kn) → T(n) = Θ(n^log_ba log^k+1n)
3. f(n) = Ω(n^{log_ba + ε}) 且正則條件 → T(n) = Θ(f(n))

使用建議

• 條件滿足直接套用結論
• 不滿足時退回遞歸樹或歸納法
• 掌握證明邏輯有助於處理變體遞歸式

總結

分治算法遞歸式求解三板斧：數學歸納法靠猜測+嚴證，遞歸樹法靠畫圖+求和，主定理靠套用+分情況。實戰中常結合使用：遞歸樹輔助猜測，歸納法嚴格證明，主定理快速驗證。掌握三法遞歸式分析不再是難題。