主定理走到路的盡頭
前一篇導覽給了你 主定理，一張針對 T(n) = a T(n/b) + f(n) 這個單一格式的快速查表。它默默的假設是「齊一性」：恰好有 a 個子問題，而且每一個都用完全相同的倍率 b 縮小。這涵蓋了極大一塊 分治遞迴關係式——但真實的演算法老是踩出格線之外。一旦你的子問題大小不一，主定理就無話可說，你只能退回去手工畫一棵遞迴樹。
經典的麻煩製造者是 中位數的中位數選擇法，這個演算法能在保證的線性時間內找出第 k 小的元素。它對兩個「不同」大小的片段遞迴：一個對約 n/5 個元素的呼叫去找樞紐，然後分割後一個對至多約 7n/10 個元素的呼叫，再加上線性的工作。這給出 T(n) = T(n/5) + T(7n/10) + Theta(n)——一條誠實的 不均切割遞迴關係式。這裡沒有單一的 b：一塊用 5 縮小，另一塊用 10/7 縮小。主定理對它甚至連敘述都辦不到，但這個演算法之所以著名，正是因為它的答案算出來是 Theta(n)。
Akra-Bazzi 的格式
Akra-Bazzi 解的是一個寬敞得多的家族。它不是只有一項 a T(n/b)，而是允許一個項的「總和」，每一項各有自己的重數與縮小倍率：T(n) = sum from i=1 to k of a_i T(n/b_i) + f(n)。這裡你可以有 k 個不同的子問題群組；群組 i 出現 a_i 次，而它每一塊的大小是 n/b_i，其中 a_i 為正、每個 b_i 嚴格大於 1。驅動工作 f(n) 允許是任何夠乖巧的函數——而關鍵在於，這方法對真實程式產生的小扭曲毫不眨眼，例如對 floor(n/2) 而非剛好 n/2 遞迴，或對 n/5 + 3 遞迴。
master theorem : T(n) = a*T(n/b) + f(n) (one b, every piece same size)
Akra-Bazzi : T(n) = SUM_i a_i*T(n/b_i) + f(n) (many b_i, pieces differ)
example (median-of-medians):
T(n) = 1*T(n/5) + 1*T(7n/10) + Theta(n)
a_1=1,b_1=5 a_2=1,b_2=10/7 f(n)=n注意到主定理不過是 k=1 的情況：一個群組，a_1 = a、b_1 = b。所以 Akra-Bazzi 不是外接上去的另一個點子——它就是同一個點子，只是把旋鈕轉到底。你學過的關於從程式碼讀出 a 與 b 的一切仍然適用；你只是讀出一整串 (a_i, b_i) 的配對，而非單一配對，正如你早已學會直接從遞迴呼叫寫出遞迴關係式那樣。
那個有魔法的指數 p
整個方法繫於一個數字，記作 p，它扮演的角色正是 臨界指數 log 以 b 為底 a 在主定理裡扮演的那個。你透過解方程式 sum from i=1 to k of (a_i / b_i^p) = 1 來求 p。用白話說：選一個次方 p，使得各子問題的大小取那個次方再相加，恰好平衡到 1。這樣的 p 永遠恰好有一個（左邊隨 p 增大而平滑遞減），而對單項的主定理情況，這方程式讀作 a / b^p = 1，也就是 a = b^p——正是熟悉的 p = log 以 b 為底 a 換了個樣子。
一旦有了 p，Akra-Bazzi 透過一條積分把答案交給你，這積分把驅動工作 f(n) 對照門檻成長率 n^p，並對所有尺度加總：T(n) = Theta( n^p * (1 + integral from 1 to n of f(u)/u^(p+1) du) )。這積分看起來嚇人，但它做的記帳跟遞迴樹一模一樣——把 f 在每一層的貢獻加總、依子問題如何繁衍來加權——只是用封閉形式呈現。前面的 n^p 是葉子貢獻的成本；積分是內部各層貢獻的成本。
- 把遞迴關係式寫成總和：讀出每個群組的重數 a_i 與縮小倍率 b_i，以及驅動工作 f(n)。
- 解 sum of a_i / b_i^p = 1 求出唯一的指數 p（單項時就是 p = log 以 b 為底 a）。
- 計算 f(u)/u^(p+1) 從 1 到 n 的積分——它告訴你是葉子還是頂層占主導。
- 讀出 T(n) = Theta( n^p * (1 + 那條積分) )；若積分收斂你得到 Theta(n^p)，若它增長你拿回 f 的貢獻。
在中位數的中位數上實際操作
取 T(n) = T(n/5) + T(7n/10) + Theta(n)。這裡兩個群組重數都是 1，b_1 = 5、b_2 = 10/7，而 f(n) = n。先從 (1/5^p) + (7/10)^p = 1 求 p。試 p = 1：那是 1/5 + 7/10 = 0.2 + 0.7 = 0.9，小於 1。由於左邊隨 p 增大而遞減，而在 p = 1 時它已經低於 1，真正的 p 必定「小於」1。所以 n^p 比 n 成長得慢，意味著線性的驅動工作 f(n) = n 壓過了葉子項。
現在算 u / u^(p+1) = u^(-p) 從 1 到 n 的積分。由於 p < 1，指數 1 - p 為正，所以這積分像 n^(1-p) 那樣增長。乘上前面的 n^p，n 的次方漂亮地相消：n^p * n^(1-p) = n^1。答案是 T(n) = Theta(n)——中位數的中位數以線性時間執行，用三行誠實的推導得出，而非一個精巧的樹論證。這種相消、其中 f(n) 是重量級而你直接得到 Theta(f(n))，正是 Akra-Bazzi 對應主定理第三種情況的版本。
誠實的限制，以及何時別伸手去拿它
Akra-Bazzi 雖通用卻非萬能，知道它的邊界很值得。它仍要求每個 b_i 嚴格大於 1——每個子問題都必須真正以某個常數倍率縮小。所以它「不」解快速排序最壞情況 T(n) = T(n-1) + Theta(n) 這類每次減一的遞迴關係式；那是 以相減縮小的遞迴關係式，而非以相除縮小，你直接展開它就得到 O(n^2)。驅動工作 f(n) 還必須滿足一個溫和的平滑條件（對它能變多快的一個界），這條件每個多項式、對數及它們的乘積都輕易滿足，但病態的振盪函數則否。
還有一個務實的提醒：一個更俐落的定理並不會改變答案「的意義」。你算出的 Theta 仍是純粹的漸進分析，所以平常的免責聲明照舊成立。大O符號隱藏常數與低階項，所以這描述的是時間如何 在 n 很大時成長，而非小規模下的判決；而你餵進去的遞迴關係式綁定於某一種 情況——中位數的中位數的 Theta(n) 是在最壞情況下贏得的，但換一個選擇法也許要問的是它的平均情況。在你信任積分的判決之前，永遠要知道你的 f(n) 與切割規模描述的是哪一種情況。
所以把兩個工具都掛在腰帶上。當遞迴關係式是乾淨的 a T(n/b) + f(n) 格式時，先伸手拿 主定理——它更快，三種情況也好記。當片段大小不一、當它們有好幾個、或當那些 +c 與向下／向上取整的雜訊讓你對主定理的附帶細則感到不安時，伸手拿 Akra-Bazzi。在用於直覺的遞迴樹、用於證明的代入法、用於速度的主定理、與用於通用性的 Akra-Bazzi 之間，你現在幾乎能解一個分治演算法丟給你的每一條遞迴關係式。