Master Theorem：遞迴式的萬用解法

為什麼需要它？

之前的章節遇到遞迴 Big-O 時都「直覺地」算：

Merge Sort：每層做 n、共 log n 層 → O(n log n)
階乘：n 次呼叫 → O(n)
費氏（沒記憶化）：每節點生 2 個 → O(2ⁿ)

但有些遞迴式不那麼直覺：

T(n) = 9T(n/3) + n² ← 多少？
T(n) = 2T(n/2) + n log n ← 多少？

Master Theorem 是一張固定公式，套進去就有答案。

適用形式

T(n) = a × T(n/b) + f(n)

a ≥ 1：每次切成 a 份子問題
b > 1：每份大小是 n/b
f(n)：合併子問題的成本

例如 Merge Sort：T(n) = 2T(n/2) + O(n) → a=2, b=2, f(n)=n。

三個案例

定義一個關鍵指標：

n^{\log_b a}

比較它和 f(n) 的成長速度，分三種情況：

Case 1：f(n) 小於 n^(log_b a)

葉節點主導——遞迴樹的葉子很多，f(n) 不夠看。

T(n) = Θ(n^(log_b a))

Case 2：f(n) 約等於 n^(log_b a)

每層成本一樣——log n 層、每層 Θ(n^(log_b a))。

T(n) = Θ(n^(log_b a) × log n)

Case 3：f(n) 大於 n^(log_b a)

根節點主導——f(n) 太大，子問題都不夠看。

T(n) = Θ(f(n))

（Case 3 還需要 regularity condition：a × f(n/b) ≤ c × f(n)，c < 1。實務上常見的 f(n) 都成立。）

直觀解釋

想像遞迴樹：

樹高 ≈ log_b(n)
葉節點數 ≈ a^(log_b n) = n^(log_b a)

每一層的總成本：

層	子問題數	每個子問題成本	該層成本
根	1	f(n)	f(n)
1	a	f(n/b)	a × f(n/b)
2	a²	f(n/b²)	a² × f(n/b²)
…	…	…	…
葉	n^(log_b a)	O(1)	n^(log_b a)

比較「葉節點層」和「根節點層」誰大：

葉節點大 → Case 1
兩者相當 → Case 2（log 多一倍）
根節點大 → Case 3

練習：套幾個

例 1：Merge Sort

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

a=2, b=2, f(n)=n
n^(log₂ 2) = n^1 = n
f(n) = n = n^(log_b a) → Case 2
答案：T(n) = Θ(n log n) ✓

例 2：Binary Search

T(n) = T(n/2) + 1

a=1, b=2, f(n)=1
n^(log₂ 1) = n^0 = 1
f(n) = 1 = 1 → Case 2
答案：T(n) = Θ(log n) ✓

例 3：

T(n) = 9T(n/3) + n²

a=9, b=3, f(n)=n²
n^(log₃ 9) = n^2 = n²
f(n) = n² = n² → Case 2
答案：T(n) = Θ(n² log n)

例 4：

T(n) = 4T(n/2) + n²

a=4, b=2, f(n)=n²
n^(log₂ 4) = n² = n²
f(n) = n² → Case 2
答案：T(n) = Θ(n² log n)

例 5：

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

a=1, b=2, f(n)=n
n^(log₂ 1) = n^0 = 1
f(n) = n 大於 1 → Case 3
答案：T(n) = Θ(n)

例 6：

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

a=4, b=2, f(n)=n
n^(log₂ 4) = n² = n²
f(n) = n 小於 n² → Case 1
答案：T(n) = Θ(n²)

Master Theorem 不適用的情況

以下情況不能直接套：

a < 1（不是分治）
b ≤ 1（子問題沒變小）
f(n) 不是多項式：例如 T(n) = 2T(n/2) + n/log n
a 不固定：例如 T(n) = T(n-1) + T(n-2) + 1（費氏，不是分治形式）

這些要用其他方法：遞迴樹法、代換法、累加法。

💡記憶口訣

比較 n^(log_b a) 和 f(n) 誰大：

f 小 → 葉節點贏 → Case 1：Θ(n^(log_b a))
一樣 → 每層相等 → Case 2：Θ(n^(log_b a) × log n)
f 大 → 根節點贏 → Case 3：Θ(f(n))

📝考試會這樣考

題型一：套 Master Theorem。 給 T(n) = aT(n/b) + f(n)，算出 Big-O。訣竅：先算 n^(log_b a)，再比 f(n)，分類。

題型二：判斷適不適用 Master Theorem。 給遞迴式，判斷能不能套（看 a, b, f(n) 形式）。

題型三：常見遞迴的記憶結果。

T(n) = 2T(n/2) + n → Merge Sort → O(n log n)
T(n) = 2T(n/2) + 1 → ? → O(n)
T(n) = T(n/2) + 1 → Binary Search → O(log n)
T(n) = T(n-1) + 1 → 階乘 → O(n)（不是分治形式）
T(n) = 2T(n-1) + 1 → 河內塔 → O(2ⁿ)

題型四：跨界情況。

Strassen 矩陣乘法：T(n) = 7T(n/2) + n² → n^(log₂ 7) ≈ n^2.807，f(n)=n² 小 → Case 1：O(n^2.807)
Karatsuba 大整數乘法：T(n) = 3T(n/2) + n → n^(log₂ 3) ≈ n^1.585，f(n)=n 小 → Case 1：O(n^1.585)

這章記住

Master Theorem 處理 T(n) = aT(n/b) + f(n) 形式。
三步：算 n^(log_b a) → 比較 f(n) → 分 Case 1/2/3。
Case 2 最常出現（兩邊相等 → 多 log n）。
不是所有遞迴都能套——遇到 T(n-1) 形式或 a 不固定，用其他方法。