一條你早已掙得的捷徑
到現在，你已經畫過夠多遞迴樹，能感覺到那個模式：每個分治成本都服從 T(n) = a T(n/b) + f(n) 這個形狀的遞迴關係式，其中 a 是你生出幾個子問題、b 是每個小了多少倍、f(n) 是你在這一層做的「分加合」工作。前面幾篇導覽裡，你用兩種方式解過這類關係式——一是把遞迴樹逐層仔細加總，二是用猜一個界再以歸納法驗證的代入法。兩者都行，但兩者每次都得做真正的算術。主定理就是回報：一次查表，就把整個家族的答案一次交給你。
整條定理只靠一個比較。T(n) = a T(n/b) + f(n) 的遞迴樹大約有 log 以 b 為底 n 那麼多層，而在最底層，葉子的數量是 n^(以 b 為底 a 的對數)——這個指數如此核心，以致它有個名字，叫臨界指數，寫作 log_b a。把它想成基準成本：堆在葉子上的工作像 n^(log_b a) 那樣成長。主定理就是讓你每層的工作 f(n) 和那個基準賽跑。哪個長得快，哪個就主宰總和——葉子贏、根贏、或打平。這三種結果就是定理的三種情形，整個構想就這麼多。
三種情形，明白說來
把這場賽跑用文字講出來。情形一（第一種情形）：葉子贏。若 f(n) 以多項式幅度慢於 n^(log_b a)——也就是對某個常數 e > 0 有 f(n) = O(n^(log_b a - e))——那麼成本就堆在樹的底部，於是 T(n) = Theta(n^(log_b a))。你往上爬時，每層的工作縮得太快，使得葉子那層把它上面的一切都比了下去。
情形二（第二種情形）：打平。若 f(n) 與基準同速成長，f(n) = Theta(n^(log_b a))，那麼樹的每一層成本都大致相同，而層數約為 log 以 b 為底 n。每層相同的工作，乘上這麼多層，就多出一個對數因子：T(n) = Theta(n^(log_b a) * log n)。這個情形解釋了為什麼合併排序的 T(n) = 2 T(n/2) + O(n) 落在 Theta(n log n)——這裡 log_b a = log_2 2 = 1，所以基準是 n，f(n) = O(n) 與它打平，於是 log n 出現了。
情形三（第三種情形）：根贏。若 f(n) 以多項式幅度快於基準，對某個 e > 0 有 f(n) = Omega(n^(log_b a + e))，那麼樹頂就是最貴的一層，它底下的一切都以幾何級數在它之下縮小，於是 T(n) = Theta(f(n))。你在最初那一次呼叫裡做的合併工作，就已經主宰了整個遞迴。情形三附帶一條額外的繩子，下一節整節都在講它。
T(n) = a T(n/b) + f(n), benchmark = n^(log_b a)
Case 1: f(n) = O(n^(log_b a - e)) -> T(n) = Theta(n^(log_b a))
Case 2: f(n) = Theta(n^(log_b a)) -> T(n) = Theta(n^(log_b a) * log n)
Case 3: f(n) = Omega(n^(log_b a + e)) -> T(n) = Theta(f(n))
and a*f(n/b) <= c*f(n) for some c < 1 (regularity)正則條件，以及夾在中間的縫隙
情形三需要一個附帶的承諾成立，叫正則條件：對某個常數 c < 1 與所有夠大的 n，有 a * f(n/b) <= c * f(n)。白話說，它保證合併工作每往下深一層，確實會按一個常數倍率縮小，於是各層成本的幾何級數被它的首項主宰，真的加總為 Theta(f(n))。對你實務上遇到的乖巧 f(n)——n 的次方，或許再乘個 log——這條件自動成立，所以很少咬人。但它不是裝飾：一個成長很快卻來回擺盪的病態 f(n) 可以滿足 Omega 的界、卻違反正則性，那時情形三就是不適用。
三個快速演練
一旦你信任它，方法就是機械式的：算出基準 n^(log_b a)，把 f(n) 與它相比，叫出情形名稱，讀出答案。讓我們把三個經典的遞迴關係式跑一遍，好讓這些情形不再抽象。
- 二分搜尋，T(n) = T(n/2) + O(1)：這裡 a = 1、b = 2，所以 log_b a = log_2 1 = 0，基準是 n^0 = 1。工作 f(n) = O(1) 與基準打平，所以這是情形二，給出 T(n) = Theta(1 * log n) = Theta(log n)。
- 卡拉楚巴乘法，T(n) = 3 T(n/2) + O(n)：這裡 a = 3、b = 2，所以 log_b a = log_2 3，約為 1.585，基準是 n^1.585。工作 f(n) = O(n) 以多項式幅度較小（n^1 對上 n^1.585，差了 n^0.585），所以情形一勝出，T(n) = Theta(n^(log_2 3))，約 Theta(n^1.585)——勝過課本的 Theta(n^2)。
- 一個合併沉重的分割，T(n) = 2 T(n/2) + O(n^2)：這裡 a = 2、b = 2，所以 log_b a = 1，基準是 n。工作 f(n) = O(n^2) 以多項式幅度較大（n^2 對上 n，差了一個 n），正則性成立（2*(n/2)^2 = n^2/2 <= c*n^2，取 c = 1/2），所以情形三適用，T(n) = Theta(n^2)——光是頂層就決定了它。
它涵蓋什麼，又不涵蓋什麼
誠實面對主定理的邊界是值得的，因為人總忍不住到處都想拿它來用。它只解恰好是 T(n) = a T(n/b) + f(n) 形式的遞迴關係式：常數個 a >= 1 的子問題、每個都是同樣規模 n/b（b > 1 為常數），以及一個表現得像多項式的 f(n)。一旦結構打破這個模子，定理就無話可說。前面遞迴導覽裡的同一個提醒在此成立：它是個強大的特例神諭，不是萬用求解器。
有兩類遞迴關係式經常落在它之外。第一，不等分割：像 T(n) = T(n/3) + T(2n/3) + O(n) 這樣的關係式，子問題大小不同，a T(n/b) 無法表達它。第二，上面附註點名的縫隙遞迴，那裡 f(n) 與基準只差一個 log 因子。對這兩者，下一篇導覽會搬出一個嚴格的推廣，Akra-Bazzi 方法，它能處理不同的碎片大小，並對合併工作做積分，在主定理聳肩之處給出答案。而在這一切底下，你最先學的遞迴樹從未失效——主定理的每一種情形，不過是一棵你早已學會逐層加總的樹，包裝好讓你不必再畫一次。