不均切割遞迴式（uneven-split recurrences）

並非每個遞迴演算法都把輸入切成相等的兩半。樞紐選得差的快速排序，可能把 n 切成規模 1 和規模 n-1 兩塊；中位數的中位數選擇法切成 n/5 和 7n/10 兩塊。當子節點的「規模不同」時，遞迴式就是「不均」的，而那個工整的主定理（它假設每個子問題都是 n/b）便不再合身。

不均切割遞迴式形如 T(n) = T(alpha n) + T(beta n) + f(n)，其中 alpha 與 beta 不同（也可能有更多項），或 T(n) = T(n/5) + T(7n/10) + Theta(n)。遞迴樹變得歪斜：不同深度的分支、不同層的葉子。你仍能對它推理。一個有用的第一步是把這些分數加起來：若往下傳的總工作比例小於 1（例如 1/5 + 7/10 = 9/10 < 1），則每層工作呈幾何級數縮小，頂層的 f(n) 往往主導，常給出 Theta(f(n))。若分數恰好加到 1 且合併是常數時間，你常會得到線性或近線性的行為。要得到精確答案，就用阿克拉-巴齊方法，它正是為不相等的 b_i 而打造的。

這些遞迴式很重要，因為不均切割很常見，有時甚至是刻意設計的：中位數的中位數刻意選 1/5 和 7/10 這兩個規模，使 1/5 + 7/10 < 1，而這正是逼出線性時間的關鍵。誠實的警告：對「大致平衡」的直覺可能誤導你。T(n) = T(n/3) + T(2n/3) + n 其實要花 Theta(n log n)（分數加起來剛好 1，所以它表現得像平衡切割），而 T(n) = T(n/5) + T(7n/10) + n 卻只花 Theta(n)——切割分數的微小變化會改變漸進行為，所以要算，別猜。