介紹

分治法是計算機科學中很重要的一種思想。英文為Divide and Conquer，直譯即為分治，或者分而治之。直觀的理解就是將一個大而難的問題分解為一些小而易的問題，先解決這些易于解決的小問題，再合并這些小問題的解（合并可以是分別求出小問題的解再合并，或者是直接將相同的小問題合并只求解一次），從而得到大問題的解。需要注意的是小問題必須和大問題是同一個類型的問題，或者說解法相同，這樣才可以遞歸求解。我們發現，這種實際上是自頂向下地分解問題。

我們可以說分治思想是被極廣泛運用的思想。
很多算法和數據結構采用了這種思想。另外計算機圖像渲染將像素點分配給GPU內的多個流處理器分別處理，最后合成出一幀的圖像；也會將一個矩陣乘法分解成n個部分分配給n個處理器并行處理。

下面介紹一些采用了分治思想的算法和數據結構。

算法

快速排序
數列每次按小于某個數（可能是數列的首尾元素或者是隨機選擇或者是三值取中法等）的和大于某個數的標準劃分為兩個子序列，但子序列內的順序和在原數列內的順序一樣，時間復雜度期望nlogn

歸并排序
將數列從中間切成兩半，分別遞歸解決兩半的排序問題，再合并解，即合并兩個有序數列，由于每次合并需要花費O(n)的時間，因此時間復雜度為O(nlogn)。

為了能更好地理解分治的思想，我們詳細介紹一下歸并排序。
比如我們定義mergeSort(array: list, from: int, to: int)為歸并排序函數，那么我們可以這么寫：

join(a: list, b) =if(either a or b is empty) b or aelseif(a[1] < b[1]) [a[1]] + join(a[2:], b)else[b[1]] + join(a, b[2:])mergeSort(array) = join(mergeSort(array[1:mid]), mergeSort(array[mid+1:]))wheremid = length(array) /2

join函數表示合并兩個有序數列，復雜度為O(n)，意思就是有兩個指針i和j一開始分別指向a和b的首元素。這是i和j之前的元素都已經被檢查過了，如果a[i] mergeSort函數就是歸并排序了，我們取中點均分了數列array到array[1..mid]和array[mid+1..n]，兩個子序列經過mergeSort后就是有序的了，這時我們花費O(n)的時間就可以合并兩個有序數列，而不需要再像選擇排序那樣每次都找一遍最值。
如果我們在紙上畫出遞歸的過程：

|---------------| |0000| |---------------| |11|22| |-------|-------| |3|4|5|6| |---|---|---|---|

數字表示遞歸方法的節點編號。
遞歸的層數最多是log2n，對于每個元素都被訪問了O(log2n)次，因此時間復雜度為O(nlogn)。

到這里讀者可能會想到log的底（或者是每次劃分的子問題個數）是不是越大越好呢？顯然不是，應該與實際問題相適應。如果劃分的子問題數過多，那么合并子問題的時候就會導致麻煩。比如歸并排序的有序數列合并，我們之前認為的O(n)的合并是基于劃分2次的。如果我們令劃分的子序列數為b，那么最終的時間復雜度是O(bnlogbn)。我們將其可以寫成