分冶法

分冶法是把一個規模為N的問題分成兩個或多個較小的與原問題類型相同的子問題，通過對子問題的求解，並把子問題的解合併起來從而構成整個問題的解，即對問題各個擊破，分而治之。如果子問題的的規模仍然相當大，仍不足以很容易的求得它的解，這時可以對此子問題重複的套用分冶策略。

定義

分冶法是把問題分成較小的與原問題類型相同的子問題。

性質

分冶法可以解決的問題有以下特徵：

（1）該問題的縮小規模到一定程度可以容易解決

（2）該問題可以分解為若干個較小的相同問題。

（3）利用該問題分解出的子問題的解可以合併為該問題的解。

（4）利用該問題分解出的各個子問題是相互獨立的，即子問題之間不該包含公共的子問題。上述的第一條特徵是絕大多數問題可以滿足的，因為問題計算的複雜性是問題規模的增加而增加；第二條特徵是套用分冶法的前提，它也是大多數問題可以滿足的。此特徵反映了遞歸思想的套用；第三條較為關鍵，能否有效利用分冶法取決於第三條特徵，如果具備了第一條和第二條特徵，而不具備第三條特徵，則可以考慮貪心法或動態規劃法；第四條特徵涉及分冶法的效率，如果各子問題是不獨立的，則分冶法要做很多不必要的工作，重複地解公共的子問題，此時雖然可以用分冶法，但一般用動態規劃法比較好。

套用

分冶策略套用比較廣泛，例如快速排序算法就是基於分冶策略的一個排序算法。對於序列A[1:N],按照分冶法的思想分析快速排序：

（1）分解 以元素A[p]為基準元素將A[p:r]劃分為三段A[p:q-1]、A[q]和A[q+1:r]，使A[p:q+1]中任何一個 元素大於等於A[q]，下標q在劃分過程中動態確定。

（2）求解通過遞歸調用快速排序算法分別對A[p:q-1]和A[q+1:r]進行排序。

（3）合併由於A[p:q-1]和A[q+1:r]的排 序都是在原位置進行的， 所以本問題就不進行任何合併操作了。

根據分冶法的分割原則，人們從大量實踐中發現在使用分冶法設計算法時，最好使子問題的規模大致相同。也就是將一個問題分成 大小相等的k個子問題的處理方法是行之有效的。許多問題可以取k=2。當然，這種使子問題大致相等的做法是出自於一種平衡子問題的思想，它總比子問題規模不等的做法要好。

過程

用分冶法編寫的過程通常包括以下幾個部分：第一 基本處理部分（即把問題分解到足夠小要進行的處理）；第二 分解問題部分；第三 遞歸調用部分；第四 合併處理部分。對於一些具體的問題，某部分彼此之間可能並無明顯界限，可能互相滲透，也可能合為一部分。但遞歸調用明顯區分於其他部分。

分冶法在每一層遞歸上面都有3個步驟：

（1）分解 將若原問題分解分解為若干個規模較小、相互獨立、與原問題形式相同的子問題。

（2）解決 若子問題規模較小而容易被解決則直接解，否則遞歸解決各個子問題。

（3）合併 將各個子問題的解合併原問題的解。

分冶法的合併是算法的關鍵所在。有些問題的合併方法比較明顯，有些問題的合併方法比較複雜，或者是有多種合併方案，或者合併方案不 明顯。究竟該怎樣合併沒有統一的模式，需要具體問題具體分析。