介紹

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

我們可以說分治思想是被極廣泛運(yùn)用的思想。
很多算法和數(shù)據(jù)結(jié)構(gòu)采用了這種思想。另外計(jì)算機(jī)圖像渲染將像素點(diǎn)分配給GPU內(nèi)的多個(gè)流處理器分別處理，最后合成出一幀的圖像；也會(huì)將一個(gè)矩陣乘法分解成n個(gè)部分分配給n個(gè)處理器并行處理。

下面介紹一些采用了分治思想的算法和數(shù)據(jù)結(jié)構(gòu)。

算法

快速排序
數(shù)列每次按小于某個(gè)數(shù)（可能是數(shù)列的首尾元素或者是隨機(jī)選擇或者是三值取中法等）的和大于某個(gè)數(shù)的標(biāo)準(zhǔn)劃分為兩個(gè)子序列，但子序列內(nèi)的順序和在原數(shù)列內(nèi)的順序一樣，時(shí)間復(fù)雜度期望nlogn

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

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

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函數(shù)表示合并兩個(gè)有序數(shù)列，復(fù)雜度為O(n)，意思就是有兩個(gè)指針i和j一開始分別指向a和b的首元素。這是i和j之前的元素都已經(jīng)被檢查過了，如果a[i] mergeSort函數(shù)就是歸并排序了，我們?nèi)≈悬c(diǎn)均分了數(shù)列array到array[1..mid]和array[mid+1..n]，兩個(gè)子序列經(jīng)過mergeSort后就是有序的了，這時(shí)我們花費(fèi)O(n)的時(shí)間就可以合并兩個(gè)有序數(shù)列，而不需要再像選擇排序那樣每次都找一遍最值。
如果我們在紙上畫出遞歸的過程：

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

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

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