分析教材用最大子段和展示了一次分治，遞迴教材列出了合併排序與快速排序，但沒有把「遞迴式怎麼解」收成可以套用的定理。本篇補上替換法的一個完整例子、遞迴樹的直覺，以及主定理的三個標準情況。
相關教材：Chapter2_Algorithm_Analysis_Teaching_Materials.md、Recursion_Teaching_Materials.md、Sorting_Algorithms_Teaching_Materials.md。
目錄
1. 分治的三步
- 分割：把大小為 (n) 的問題切成若干個較小的同類問題。
- 解決：子問題小到可以直接算；否則遞迴。
- 合併：把子問題的答案合成原問題的答案。
動態規劃和它的差別在於子問題是否重疊。分治的左右兩半不該依賴彼此的中間結果以外的重複計算。若同一題被問很多次，改看 DP 教材。
2. 遞迴式從哪裡來
合併排序把陣列切成兩半，兩邊各做一次，再花 (\Theta(n)) 合併：
[ T(n) = 2T(n/2) + \Theta(n), \quad T(1) = \Theta(1) ]
一般形式是 (a) 個子問題，每個是原來的 (1/b)，合併成本 (f(n))：
[ T(n) = a\,T(n/b) + f(n) ]
(a \ge 1)、(b > 1)。快速排序的最壞情況不是這個形狀（子問題大小是 (n-1) 和 (0)），所以主定理管不到那個最壞情況。它的平均情況需要別的論證。
3. 替換法
猜一個上界，再用歸納法證明。
猜 (T(n) \le cn\log_2 n) 能滿足 (T(n) = 2T(n/2) + n)（先把 (\Theta(n)) 寫成 (n)，底數換掉只影響常數）。
[ T(n) \le 2\cdot c\cdot\frac{n}{2}\log_2\frac{n}{2} + n = cn(\log_2 n - 1) + n = cn\log_2 n - cn + n ]
要 (\le cn\log_2 n)，需要 (-cn + n \le 0)，也就是 (c \ge 1)。基底 (n=2) 時單獨檢查常數是否夠大。
替換法的困難是「猜」。遞迴樹用來產生那個猜。
4. 遞迴樹
(T(n) = 2T(n/2) + n) 的樹：
- 第 0 層成本 (n)
- 第 1 層兩個節點，各 (n/2)，合計 (n)
- 第 (i) 層 (2^i) 個節點，各 (n/2^i)，合計仍是 (n)
- 約 (\log_2 n) 層
總成本 (n\log_2 n)。這和替換法的猜一致。
若是 (T(n) = 2T(n/2) + n^2)：第 (i) 層合計 (2^i \cdot (n/2^i)^2 = n^2 / 2^i)。這是等比級數，根的 (n^2) 佔主導，總和 (\Theta(n^2))。
葉子有多少：深度 (\log_b n)，葉子數 (a^{\log_b n} = n^{\log_b a})。葉子貢獻 (\Theta(n^{\log_b a}))。主定理就是在比「葉子」和「內部合併成本」誰比較大。
5. 主定理
令 (T(n) = aT(n/b) + f(n))，(c_{\mathrm{crit}} = \log_b a)。比較 (f(n)) 和 (n^{c_{\mathrm{crit}}})。
情況 1。 (f(n) = O(n^{c_{\mathrm{crit}} - \varepsilon}))，(\varepsilon > 0)。葉子比合併貴。
[ T(n) = \Theta(n^{\log_b a}) ]
情況 2。 (f(n) = \Theta(n^{c_{\mathrm{crit}}} \log^k n))，(k \ge 0)。每一層（再乘上對數的次方）一樣重。
[ T(n) = \Theta(n^{\log_b a} \log^{k+1} n) ]
(k=0) 就是最常見的 (\Theta(n^{\log_b a}\log n))。合併排序是 (a=2,b=2,f(n)=\Theta(n))，(c_{\mathrm{crit}}=1)，(k=0)，所以 (T(n)=\Theta(n\log n))。
情況 3。 (f(n) = \Omega(n^{c_{\mathrm{crit}}+\varepsilon}))，而且對足夠大的 (n) 有正規條件 (a f(n/b) \le c f(n))，其中常數 (c<1)。根的合併比所有葉子貴。
[ T(n) = \Theta(f(n)) ]
(T(n)=2T(n/2)+n^2)：(c_{\mathrm{crit}}=1)，(f=n^2) 多出一個多項式因子。正規條件 (2\cdot(n/2)^2 = n^2/2 \le c n^2) 對 (c=1/2) 成立。所以 (T(n)=\Theta(n^2))。
6. 三個不能直接套的例子
- 差距不是多項式。 (f(n) = n\log n)、(a=2)、(b=2) 時，(f(n)/n = \log n) 比任何 (n^{\varepsilon}) 都慢，也不是 (\Theta(1))。它落在情況 2 的 (k=1)：(T(n)=\Theta(n\log^2 n))。若只背「三個情況」卻忘了 (\log^k)，會以為定理失靈。
- 子問題大小差很遠。 (T(n)=T(n-1)+T(n/2)+n) 不是 (aT(n/b))。用遞迴樹或 Akra–Bazzi，不要硬套。
- 快速排序最壞。 (T(n)=T(n-1)+\Theta(n)=\Theta(n^2))，主定理的 (b) 必須是大於 1 的常數比例，(n-1) 不是 (n/b)。
7. 計數逆序對
逆序對是 (i
- 左半的逆序對，遞迴。
- 右半的逆序對，遞迴。
- 跨左右的逆序對：合併時，若右邊的 (y) 先被取出，則左半還沒取出的每一個都和 (y) 形成逆序對。
合併仍是 (\Theta(n))，遞迴式與合併排序相同，所以 (O(n\log n))。二重迴圈是 (O(n^2))。
例：[2, 4, 1, 3]。
- 左
[2,4]逆序對 0；右[1,3]逆序對 0。 - 合併：取出
1時左半還有2,4，貢獻 2；取出2；取出3時左半還有4，貢獻 1。 - 跨邊 3 對：
(2,1), (4,1), (4,3)。總數 3。
8. 常見陷阱
- 把底數當成要背的常數。 (\log_b a) 的底是子問題縮小的倍率 (b)，不是 2。(a=3,b=2) 時臨界指數是 (\log_2 3 \approx 1.585)。
- 情況 3 忘了正規條件。 多項式都滿足；人為造出的 (f) 可能在子問題上突然變大，定理不適用。
- 地板與天花板。 (n/2) 寫成 (\lfloor n/2\rfloor) 不改變主定理的結論，歸納時會多出一堆低階項，替換法要把那些項吸收進常數。
- 把主定理用在空間。 合併排序的額外空間是 (\Theta(n))，不是 (n\log n)。時間的遞迴式和空間的遞迴式要分開寫。
9. 練習題
- (T(n)=8T(n/2)+n^2)。屬於哪一種情況？答案的階是什麼？
- (T(n)=2T(n/2)+n\log n)。(k) 是多少？
- 為什麼二元搜尋的 (T(n)=T(n/2)+\Theta(1)) 是 (\Theta(\log n))，而不是 (\Theta(n))？
- 用手算
[3, 1, 2]的逆序對，並標出哪些是跨邊產生的。 - Strassen 矩陣乘法是 (T(n)=7T(n/2)+\Theta(n^2))。它比直接的 (\Theta(n^3)) 好在哪一個指數？
參考答案
- (c_{\mathrm{crit}}=\log_2 8=3)，(f(n)=n^2 = O(n^{3-\varepsilon}))，情況 1，(T(n)=\Theta(n^3))。
- (c_{\mathrm{crit}}=1)，(f(n)=\Theta(n\log^1 n))，所以 (k=1)，(T(n)=\Theta(n\log^2 n))。
- (a=1,b=2)，(c_{\mathrm{crit}}=0)，(f(n)=\Theta(1)=\Theta(n^0))，情況 2 且 (k=0)，(T(n)=\Theta(\log n))。只有一個子問題，葉子只有一片，成本來自 (\log n) 層的常數工作。
- 逆序對是
(3,1), (3,2)，共 2。左[3]、右[1,2]內部都是 0；兩對都是跨邊。 - (c_{\mathrm{crit}}=\log_2 7 \approx 2.807)，(n^2) 屬於情況 1，所以 (T(n)=\Theta(n^{\log_2 7}))，指數小於 3。
小結
分治的時間由 (T(n)=aT(n/b)+f(n)) 決定。先看 (n^{\log_b a}) 和 (f(n)) 誰大：葉子主導、每一層打平、或根的合併主導。合併排序、二元搜尋、一層 (n^2) 的分治分別對上這三種。子問題不是固定比例縮小時，不要套主定理。逆序對說明分治的合併步驟可以順便做比較排序以外的工作，複雜度仍跟合併排序一樣。