分治算法思想介紹

一，介紹

分治算法主要包含兩個步驟：分、治。分，就是遞歸地将原問題分解成小問題；治則是：在解決了各個小問題之後(各個擊破之後)合并小問題的解，進而得到整個問題的解

二，分治遞歸表達式

分治算法一般都可以寫出一個遞歸表達式；比如經典的歸并排序的遞歸表達式：T(N)=2T(N/2)+O(N)

T(N)代表整個原問題，采用了分治解決方案後，它可以表示成：

①分解成了兩個規模隻有原來一半(N/2)的子問題:T(N/2)

②當解決完這兩個子問題T(N/2)之後，再合并這兩個子問題需要的代價是 O(N)

遞歸表達式的解就是該算法的時間複雜度。關于某些特定形式的遞歸表達式，求解時，是可以直接套公式的：

T(N)=aT(N/b)+Θ(N^K) 表示将原問題分解成 a 個 規模大小為 N/b 的子問題，合并這 a 個子問題的代價是 Θ(N^K)  （N^k 表示 N 的 k 次方）

T(N)的解有以下三種情況：

1) T(N)=O(N^logba)   當 a > bk 時

2) T(N)=O(Nk logN)   當 a = bk 時

3) T(N)=O(Nk)   當 a < bk 時

三，分治算法的一些執行個體分析

①最近點問題，參考《資料結構與算法分析》Mark Allen Wiess著 第10章

問題描述：在一個平面上分布着若幹個點，點與點之間的距離公式為：[(x1-x2)2 + (y1-y2)2]1/2

找出，距離最小的那兩個點

假設平面上有N個點，這N個點之間共有 1+2+3+……+(N-1) = N(N-1)/2 個距離，采用窮舉，時間複雜度為O(N^2)；而采用分治則可以做到O(NlogN)

那如何應用分治呢？

首先将N個點按照 X軸坐标進行排序，排序算法的時間複雜度為O(NlogN)，故相對于窮舉而言，它不影響總是時間複雜度。因為O(NlogN) << O(N^2)（遠遠小于）

按X軸坐标排序後，可以劃一條垂直于X軸的線，将所有的點劃分成兩半。那麼，點與點之間的距離就會出現三種情況：

a)兩個點完全處于垂線的左邊，那麼這兩點的距離不會越過垂線，這類距離記為 DL

b)兩個點完全處于垂線的右邊，那麼這兩點的距離不會越過垂線,這類距離記為 DR

c)兩個點一個在垂線的左邊，一個在垂線的右邊，是以這兩個的距離會橫跨垂線

設 minD = min{DL，DR}，即minD是 a)  和 b) 這兩種情況下的所有距離中最小的那個距離。

那麼，可以用數學證明：處于[-minD, minD]這個範圍内的點平均隻有 O(sqrt(N))個。

而sqrt(N)個點，一共有 O(N)個距離對，因為N個點一共有N(N-1)/2，即O(N^2)個距離對

這樣，我們可以将處于 c) 中的點對距離 采用窮舉來查找出最小的距離，複雜度為O(N)

而，處于a) 和 b) 中的點可以 繼續進行遞歸劃分。

進而，遞歸表達式為： T(N)=2T(N/2)+O(N) ，而這個表達式的解為：T(N)=O(NlogN)

也就是說，采用了分治，成功地将原問題從O(N^2) 降低為 O(NlogN)

②K選擇問題

問題描述：給出N個數，找出其中第K小的元素

如果直接用窮舉，一共需要比較K*N次，當K與N有關時，比如K是中位數(K=N/2)，時間複雜度為O(N^2).

而采用分治，則可把複雜度降低為O(N)

首先在N個數選出一個樞軸元素，将比樞軸元素的元素放到 樞軸元素的右邊，将比樞軸元素小的元素放到樞軸元素的左邊。這樣，把N個數，分成了兩部分，一部分，記為S(1) 它們都比樞軸大，另一部分記為S(2)，它們都比樞軸小。這就是分治 的 分。

假設一種理想的情況：樞軸元素 基本位于中間值，即它 總是将原數組劃分成兩個兩個大小基本相等的子數組：S(1) 和 S(2)

要求解第K小的元素，有三種情況：

a) 若 K < |S(1)|，說明：第K小的元素位于 S(1)這個子數組中。   其中，|S(1)| 表示 S(1) 數組中元素的個數。

b) 若 K == |S(1)| + 1，說明：第K小的元素，剛好是樞軸元素

c) 否則，第K個的元素位于 S(2)子數組中

如果是情況 a) 或者 情況 c) ，可以繼續遞歸分解子數組。

分解問題之後：将N個元素，分成了兩個 N/2 個元素的子數組，隻需要在其中一個子數組中進行查找即可，使用窮舉查找，複雜度為O(N/2)。

遞歸表達式： T(N)=T(N/2)+O(N/2)，這個遞歸表達式的解為O(N)

這說明，采用分治，可以将K選擇問題的時間複雜度降低為O(N)

順便說一句，這與快速排序的劃分非常的相似，隻不過快速排序需要處理兩個子數組（對劃分的兩個子數組分别進行快速排序）。而這裡隻需要處理其中某一個子數組，因為若第K小元素處于S(1)子數組中，那麼它一定不會在S(2)子數組中了，是以我們就不需要再處理S(2)子數組了。

原文：http://www.cnblogs.com/hapjin/p/5538912.html

本文轉自hapjin部落格園部落格，原文連結：http://www.cnblogs.com/hapjin/p/5538912.html，如需轉載請自行聯系原作者