工具-遞迴式與主定理

🎯 什麼情境該想到我

分工：主定理三種情況的精確條件（含 ε 與正則條件）、套用範例、Karatsuba 與 Strassen → 分治法。這張補主定理管不到的遞迴式——這些在實務和面試中出現得更頻繁。

當你有一個分治/遞迴演算法，想算它的時間複雜度（如「為什麼合併排序是 O(n log n)」）時。

⚙️ 怎麼用

1. 寫出遞迴式：T(n) = a·T(n/b) + f(n)（拆成 a 個大小 n/b 的子問題，合併成本 f(n)）。
2. 用主定理（Master Theorem）比較 f(n) 與 n^(log_b a)：
   • f(n) 較小 → T(n) = Θ(n^(log_b a))
   • 兩者同量級 → T(n) = Θ(n^(log_b a)·log n)（如合併排序 a=2,b=2 → n log n）
   • f(n) 較大（且規則）→ T(n) = Θ(f(n))
3. 主定理不適用時，用遞迴樹畫出來加總，或用代入法猜測並歸納證明。

★ 主定理管不到的：「減一」型遞迴式速查表

主定理只處理 T(n) = a·T(n/b) + f(n)（除以 b）。但很多遞迴是減掉常數：

遞迴式	結果	典型例子
$T(n)=T(n-1)+O(1)$	$O(n)$	遞迴走訪鏈結串列、遞迴求陣列總和
$T(n)=T(n-1)+O(n)$	$O(n^2)$	選擇排序；快速排序的最壞情況（每次樞紐都選到極值）
$T(n)=2T(n-1)+O(1)$	$O(2^n)$	河內塔；列舉所有子集
$T(n)=T(n-1)+T(n-2)+O(1)$	$O({\phi }^n)\approx O(1.618^n)$	沒有記憶化的 Fibonacci
$T(n)=n\cdot T(n-1)$	$O(n!)$	列舉所有排列

推導方法（展開法）：以 $T(n)=T(n-1)+n$ 為例

$T(n)=n+(n-1)+(n-2)+\cdots +1=\frac{n(n+1)}{2}=O(n^2)$

★ 其他常見但不標準的遞迴式

遞迴式	結果	例子	怎麼算
$T(n)=T(n/2)+O(n)$	$O(n)$	Quickselect 的期望情況（找第 k 小）	遞迴樹：$n+n/2+n/4+\cdots <2n$
$T(n)=T(n/3)+T(2n/3)+O(n)$	$O(n\log n)$	不均勻切割	遞迴樹：每層總和 ≤ n，最深 ${\log }_{3/2}n$ 層
$T(n)=T(\sqrt{n})+O(1)$	$O(\log \log n)$	van Emde Boas 樹	變數代換：令 $n=2^m$
$T(n)=2T(n/2)+O(n\log n)$	$O(n{\log }^{2}n)$	落在主定理 case 2 和 3 的縫隙	遞迴樹：第 i 層成本 $n\log (n/2^i)$，加總

★ 遞迴樹：萬用的手算法

主定理背不起來時，畫樹就好：

1. 根：成本 f(n)。
2. 每一層：有 $a^i$ 個節點，每個大小 $n/b^i$，這層總成本 $a^i\cdot f(n/b^i)$。
3. 層數：${\log }_{b}n$。
4. 加總所有層。

判斷誰主導：每層成本往下遞增 → 葉子主導（case 1）；每層一樣 → 乘上層數得 $\log n$（case 2）；每層遞減 → 根主導（case 3）。主定理只是這個畫樹過程的結論。

★ 記憶化如何改變遞迴式

沒有記憶化的 Fibonacci 是 $T(n)=T(n-1)+T(n-2)+O(1)$，指數級。加上記憶化之後，每個子問題只算一次：總共 n 個不同的子問題，每個 O(1) → O(n)。

判斷規則：有記憶化時，複雜度 = （不同子問題的數量）×（每個子問題不含遞迴的成本）。這是分析動態規劃的標準方法（見 動態規劃）。

★ 別忘了空間：遞迴深度就是堆疊用量

• $T(n)=T(n-1)+\dots$ 的遞迴深度是 n。Go 的 goroutine 堆疊會自動成長，但深度到百萬級會用掉大量記憶體；超過上限（64 位元系統預設 1 GB）時程式直接 fatal error。
• $T(n)=2T(n/2)+\dots$ 的深度只有 log n，幾乎不會有堆疊問題。
• 深度可能很大的遞迴，改寫成迴圈加顯式的堆疊（見 深度優先搜尋）。

🧪 我實際套用的紀錄

• 2026-07-15：（待填）

⚠️ 注意

• 主定理有適用前提（子問題等分、f(n) 行為規則）；不符時別硬套，改用遞迴樹。

🔗 相關工具

• 工具-時間複雜度分析 —— 上位工具，主定理是它在遞迴演算法上的專用解法
• 工具-演算法設計策略 —— 使用場合，凡是走分治路線的設計都要靠遞迴式算出代價
• 工具-迴圈不變式 —— 姊妹工具，一個算成本，一個證正確，兩者一起才算把演算法看完