自頂向下和逐步求精

介紹

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

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

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

算法

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

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

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

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

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