分、治、合：那個範本

一個構想，三個動作

在暴力法那一階，你見過正面迎擊問題的演算法：列出每一種可能再逐一檢查。分治法採取相反的姿態。它不直接攻打規模為 n 的輸入，而是把問題切成幾塊同類型的小問題，解掉它們，再把答案縫回去。整套分 / 治 / 合範本不過三個動作：分——把輸入切成幾個子問題；治——用遞迴解掉每個子問題；合——把它們的解組裝成原問題的解。你即將遇到的幾乎每個快速演算法——排序、搜尋、大數相乘——都是這同一副骨架換了件外衣。

「治」這一步是魔法藏身之處，因為它是遞迴的：要解掉一個規模 n/2 的子問題，我們對它施加同樣的三個動作，於是它又被切開，再切開，直到碎片小到答案一目了然。那個我們停手、直接作答的最小情形——只有一個元素的清單已經排好序、單一個數字就是它自己的乘積——就是基底情形。沒有它，遞迴會永遠墜落；有了它，切分觸底，答案便開始往上回流。

寫成食譜的話，一個 solve 常式每次都是同樣那五行：若輸入夠小，就直接回傳答案（基底情形）；否則把它分成子問題 P1、P2、…（分），對每個遞迴呼叫 solve 得到 S1、S2、…（治），再回傳 combine(S1, S2, …)（合）。把這副骨架背下來，因為本階每個演算法都只是填三個空格——怎麼分、基底情形是什麼、怎麼合——而遞迴的管線始終不變。

為什麼那些碎片不能重疊

有一個讓整套方案站得住腳的安靜假設，值得把它說出來。要讓分治法划算，子問題應該是彼此獨立的——每塊能各自獨立解掉，彼此之間沒有共用的工作。當你排序陣列的左半部時，那份工作對排序右半部既沒有任何啟示，也不會被它重複利用。正是這份獨立性，讓我們能乾淨地把成本相加：總共的「治」成本就是左邊呼叫的成本加上右邊呼叫的成本，沒有重疊要被重複計算。

注意三個動作之間的分工。分這一步通常很便宜——往往只是挑一個中點。治這一步本身不做真正的工作；它只是把問題委派給較小的副本。所以巧思（通常還有成本）都住在合步驟裡：把兩個已解的半邊融合成一個已解的整體，要花多少力氣。出人意料地，許多演算法設計歸結為一個問題——我能不能讓合更便宜？——而接下來的指南，大半都是回答這個問題的變奏。

從食譜到執行時間

一個分治演算法有多快？我們不能只數迴圈，因為工作散落在一棵遞迴呼叫的樹上。取而代之，我們寫下一條遞迴關係式：一條把規模 n 的成本，用各個較小碎片的成本來定義的方程式。若我們切成 a 個子問題、每個規模 n/b，而遞迴之外的「分加合」工作要花 f(n)，那麼成本滿足 T(n) = a T(n/b) + f(n)。這一行就抓住了整個演算法的形狀：a 數的是分支數、b 說每塊小了多少倍、f(n) 是這一層分與合的代價。

T(n) = a * T(n/b) + f(n)        # a branches, each of size n/b, plus f(n) outside

  merge sort:   T(n) = 2 T(n/2) + O(n)      # split in 2, merge costs O(n)
  binary search: T(n) = 1 T(n/2) + O(1)     # one half survives, O(1) to pick it

要把那條遞迴關係式變成像 O(n log n) 這樣乾淨的界，最直覺的工具是遞迴樹。把最上層的呼叫畫成一個成本為 f(n) 的節點；它下面畫出 a 個子節點、各花 f(n/b)；再下面是它們的子節點；如此一路畫到基底情形。現在逐層把成本加起來。執行時間就是所有層的總和，而這個總和的形狀——是被頂層主宰、是平均攤開、還是堆在葉子上——就告訴你答案。這是一幅你真的能直接讀出執行時間的圖。

讀一棵遞迴樹：合併排序

讓我們用遞迴關係式 T(n) = 2 T(n/2) + O(n)——合併排序的招牌——把這棵樹具體化。頂層節點花約 n（合併兩個總長 n 的已排序半邊的工作）。它有兩個規模 n/2 的子節點，各花約 n/2——加起來又是 n。那四個規模 n/4 的孫節點各花約 n/4——再一次加起來是 n。無論我們往下挖多深，每一整層都加總成同一個 n。這正是這條遞迴關係式給出 n log n 的核心理由。

1. 樹的每一層都加總成約 n 的總工作，因為規模減半會讓節點數加倍——兩個效果互相抵消。
2. 從 n 出發、每層減半，大約要 log n 層才會縮到規模為 1 的基底情形。
3. 相乘：每層約 n 的工作乘上約 log n 層，總共約 n log n。
4. 於是 T(n) = 2 T(n/2) + O(n) 解出 Theta(n log n)——分治排序那著名的成本。

把它和二分搜尋對照，後者的遞迴關係式是 T(n) = T(n/2) + O(1)。這裡我們只做「一個」遞迴呼叫，不是兩個——與中間元素比較後，我們丟掉一整個半邊，只對倖存的那半遞迴。這棵樹不是濃密的，而是一條細細的單一路徑，每層 O(1) 工作、約 log n 層，整體給出 O(log n)。同一個範本，但因為我們是丟掉一半輸入、而非鑽進兩半，成本就從 n log n 一路塌縮到 log n。你保留幾個分支，決定了一切。

捷徑，以及它在哪裡止步

每次都畫一棵樹很累，所以有條捷徑：主定理。對於恰好是 T(n) = a T(n/b) + f(n) 形式的遞迴關係式，它靠比較兩個成長率來直接讀出答案——你每層做的工作 f(n)，對上由分支增殖速度設定的基準 n^(以 b 為底 a 的對數)。哪個長得快，哪個就贏，並決定總和；當兩者打平時，會多冒出一個 log n 因子（那個平手正是合併排序的情形 T(n) = 2 T(n/2) + O(n)，也正是排序為何落在 Theta(n log n) 的原因）。遞迴關係式那一階後面的指南會把這講精確；現在，就把它當成你一直手畫的那些樹的快速神諭。

兩個誠實的提醒收尾。第一，把遞迴關係式列對，並不證明演算法正確——它只告訴你成本。正確性仍仰賴合步驟確實把兩個正確的子解融合成一個正確的整體，這要用對遞迴呼叫的歸納法來證：假設較小的呼叫回傳正確答案，再證明合保住了正確性。第二，這一切都是漸進的：一個 Theta(n log n) 的分治法，在極小的輸入上仍可能輸給一個簡單的平方法，因為遞迴的記帳帶著真實的每次呼叫開銷，被隱藏常數悄悄吸收掉了。這正是為什麼正式的排序常式一旦碎片變小，就改用插入排序。