🎯 什麼情境該想到我
當你有一個分治/遞迴演算法，想算它的時間複雜度（如「為什麼合併排序是 O(n log n)」）時。
⚙️ 怎麼用
- 寫出遞迴式：
T(n) = a·T(n/b) + f(n)（拆成 a 個大小 n/b 的子問題，合併成本 f(n)）。 - 用主定理（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))
- 主定理不適用時，用遞迴樹畫出來加總，或用代入法猜測並歸納證明。
🧪 我實際套用的紀錄
- 2026-07-15：（待填）
⚠️ 注意
- 主定理有適用前提（子問題等分、f(n) 行為規則）；不符時別硬套，改用遞迴樹。
🔗 相關工具
- 工具-時間複雜度分析 —— 上位工具，主定理是它在遞迴演算法上的專用解法
- 工具-演算法設計策略 —— 使用場合，凡是走分治路線的設計都要靠遞迴式算出代價
- 工具-迴圈不變式 —— 姊妹工具，一個算成本，一個證正確，兩者一起才算把演算法看完