理論與進階主題
主定理
主定理是求解一類非常常見的遞迴式的「食譜」：T(n) = aT(n/b) + f(n)。這裡 a 是你產生的子問題個數，b 是每個子問題縮小的倍數，f(n) 是遞迴呼叫之外要做的額外工作——拆分和合併。許多分治演算法恰好就是這個形狀，於是你不必每次從頭求解，只要比較兩個量就能讀出答案。
要比較的兩個量是：f(n)——一層上所做的工作，與 n^(log_b a)——衡量葉子層子問題個數增長得有多快。定理分三種情形。情形一：若葉子工作 n^(log_b a) 比 f(n) 增長得更快，遞迴的底層佔主導，T(n) = O(n^(log_b a))。情形二：若兩者增速相同，每一層的代價都差不多，而你要在全部 log n 層上付這份代價，於是 T(n) = O(n^(log_b a) · log n)。情形三：若 f(n) 增長得更快，頂層佔主導，T(n) = O(f(n))。
合併排序是教科書式的契合：T(n) = 2T(n/2) + O(n)，故 a = 2、b = 2，n^(log_b a) = n^(log_2 2) = n。合併工作 f(n) = O(n) 與 n 增速相同，正是情形二——每層代價 O(n)，共 log n 層，總計 O(n log n)。一句老實話：主定理只涵蓋這種特定形狀、且子問題大小大致相等的遞迴，情形三還需要一個溫和的「正則性」條件。當遞迴不符合此形時，退回到遞迴樹或歸納法。
// T(n) = a*T(n/b) + f(n) // Compare f(n) with n^(log_b a): // case 1: f(n) smaller -> T = O(n^(log_b a)) // case 2: same rate -> T = O(n^(log_b a) * log n) // case 3: f(n) larger -> T = O(f(n)) // // merge sort: a=2, b=2 -> n^(log2 2) = n; f(n)=n -> case 2 // => T(n) = O(n log n)
合併排序：a=2、b=2、f(n)=n、n^(log_b a)=n → 情形二 → O(n log n)。
它只適用於 T(n) = aT(n/b) + f(n) 這種、子問題大致等大的遞迴；其他形狀要用遞迴樹或歸納法。
又稱
另見