Master Theorem遞迴式求解

01為什麼需要它

看到這些關鍵字就想到它：T(n) = aT(n/b) + f(n)、切成幾份、每份縮小幾倍、遞迴樹、分治的複雜度是多少。

02核心概念

分治演算法的時間都長成同一個形狀：T(n) = a·T(n/b) + f(n)。a 是切成幾個子問題，b 是每個子問題縮小幾倍，f(n) 是切開和合併的成本。這一課只處理 f(n) = Θ(n^d) 的多項式情況，這已經涵蓋絕大多數你會遇到的分治。

想像遞迴樹。第 i 層有 a^i 個子問題，每個大小 n/b^i，所以第 i 層的總工作量是 a^i × (n/b^i)^d = n^d × (a/b^d)^i。這是一個公比 r = a/b^d 的等比數列。等比數列的總和由公比決定：r 大於 1 時最後一項最大，r 等於 1 時每項一樣，r 小於 1 時第一項最大。這就是三種情況的來源。

比較 log_b a（葉子數的指數）和 d（根的工作量指數），等價於比較 r 和 1。情況 1：log_b a > d，葉子主導，T(n) = Θ(n^(log_b a))，例如 Strassen 的 n^2.81。情況 2：log_b a = d，每層工作量都是 n^d，共 log n 層，T(n) = Θ(n^d log n)，例如合併排序的 n log n、二分搜尋的 log n。情況 3：log_b a < d，根主導，T(n) = Θ(n^d)，例如切半但合併要 n² 的演算法，遞迴根本沒幫上忙。

常見誤區：以為「有切半就是 log n」。切半只保證層數是 log n，總時間還要看每層做多少事。另外定理不涵蓋 f(n) 不是多項式的情況（例如 T(n) = 2T(n/2) + n log n 卡在情況 2 和 3 之間），也不涵蓋子問題不是按比例縮小的情況（例如快速排序最壞情況的 T(n) = T(n−1) + n，每次只少一個），或子問題大小不一樣的情況（例如 T(n) = T(n/3) + T(2n/3) + n）。這些要回頭畫遞迴樹或用代換法。

03演算法步驟

1. 1從程式碼讀出 a（遞迴呼叫幾次）、b（每次傳入的大小縮小幾倍）、d（遞迴以外的工作是 n 的幾次方）。
2. 2算 log_b a。a = 1 時是 0，a = b 時是 1，a = b² 時是 2；其他情況用計算機，例如 log₂ 7 ≈ 2.81。
3. 3比較 log_b a 與 d。大於：情況 1，答案 Θ(n^(log_b a))。等於：情況 2，答案 Θ(n^d log n)。小於：情況 3，答案 Θ(n^d)。
4. 4用遞迴樹檢查直覺：算第 0 層、第 1 層、第 2 層的工作量，看是在變大、持平還是變小。方向要和你選的情況一致。
5. 5若 f(n) 不是純多項式，或子問題大小不均，定理不適用。改畫遞迴樹逐層加總，或猜答案再用歸納法驗證。

04互動示範

選一個常見演算法，或自己組合 a、b、d。上方顯示比較與結論，下方是遞迴樹每一層的工作量：情況 1 的長條逐層變長，情況 2 每層一樣長，情況 3 逐層變短。注意根那層和葉子那層各占總量的比例。

05程式碼

定理本身不是演算法，這裡的程式碼是一個小計算器：輸入 a、b、d 回傳情況與複雜度，再用遞迴樹逐層加總驗證，看 n 加倍時總工作量放大幾倍。

import math


def npow(d):
    """n^d 的顯示：n^0 寫 1、n^1 寫 n"""
    return "1" if d == 0 else "n" if d == 1 else f"n^{d}"


def master(a, b, d):
    """T(n) = a·T(n/b) + Θ(n^d) 的解。回傳 (情況, 複雜度字串)。
    比較 log_b(a) 與 d：
      大於 → 葉子主導，Θ(n^log_b a)
      等於 → 每層一樣多，Θ(n^d · log n)
      小於 → 根主導，Θ(n^d)
    """
    e = math.log(a, b)                      # 葉子數的指數 log_b a
    if abs(e - d) < 1e-9:
        return 2, "Θ(log n)" if d == 0 else f"Θ({npow(d)} log n)"
    if e > d:
        return 1, f"Θ(n^{e:.2f})"
    return 3, f"Θ({npow(d)})"


# 用遞迴樹逐層加總，驗證定理給的答案
def recursion_tree(a, b, d, n):
    total, size, nodes = 0, n, 1
    while size >= 1:
        total += nodes * size ** d          # 這一層：nodes 個子問題，每個花 size^d
        nodes *= a
        size /= b
    return total


if __name__ == "__main__":
    for name, (a, b, d) in {
        "合併排序": (2, 2, 1),
        "二分搜尋": (1, 2, 0),
        "Karatsuba": (3, 2, 1),
        "Strassen": (7, 2, 2),
    }.items():
        case, ans = master(a, b, d)
        print(f"{name}: T(n) = {'' if a == 1 else a}T(n/{b}) + {npow(d)} → 情況 {case}，{ans}")
    # 合併排序: T(n) = 2T(n/2) + n → 情況 2，Θ(n log n)
    # 二分搜尋: T(n) = T(n/2) + 1 → 情況 2，Θ(log n)
    # Karatsuba: T(n) = 3T(n/2) + n → 情況 1，Θ(n^1.58)
    # Strassen: T(n) = 7T(n/2) + n^2 → 情況 1，Θ(n^2.81)

    # n 從 1024 加倍到 2048，看總工作量放大幾倍：
    # 合併排序約 2.2 倍（n log n 在 n 加倍時略多於 2 倍），Strassen 約 7 倍（n^2.81）
    for a, b, d in [(2, 2, 1), (7, 2, 2)]:
        r = recursion_tree(a, b, d, 2048) / recursion_tree(a, b, d, 1024)
        print(f"a={a} b={b} d={d}: n 加倍，工作量 ×{r:.2f}")   # ×2.18、×7.01

06練習題

• LeetCode 704Binary Search（T(n) = T(n/2) + 1）Easy
• LeetCode 912Sort an Array（寫合併排序，推 T(n) = 2T(n/2) + n）Medium
• LeetCode 50Pow(x, n)（T(n) = T(n/2) + 1）Medium
• LeetCode 241Different Ways to Add Parentheses（子問題不均，定理不適用）Medium
• LeetCode 932Beautiful Array（T(n) = 2T(n/2) + n）Medium
• LeetCode 218The Skyline Problem（分治版 T(n) = 2T(n/2) + n）Hard