|
這篇文章將討論：
1） 分治策略的思想和理論
2） 幾個分治策略的例子：合并排序,，快速排序,，折半查找，二叉遍歷樹及其相關(guān)特性,。
說明：這幾個例子在前面都寫過了,，這里又拿出來，從算法設(shè)計的策略的角度把它們放在一起來比較,，看看分治是如何實現(xiàn)滴,。
由于內(nèi)容太多，我將再花一篇文章來寫4個之前沒有寫過的分治算法：1,，大整數(shù)乘法 2,，矩陣乘法的分治策略 3，最近點(diǎn)對 4,，凸包問題,，請見下一篇。
好了,，切入正題,。
---------------------------------------------------------------------------------------------------------------------------------------------------
分治算法是按照下列方案來工作的：
1）將問題的實例劃分為幾個較小的實例，最好具有相等的規(guī)模（事實上,，一般來說就是這樣來分的,，而且分為2個實例的居多，注意是遞歸的分?。,?！）
2）對這些較小的實例求解（一般使用遞歸的方法，但在問題規(guī)模足夠小的時候也可以采用采用另一個算法（停止遞歸））
3）如果有必要的話,，合并這些較小問題的解,，以得到原始問題的解（事實上，一個分治算法的精華就在于合并解的過程）
不要忽視這三句話?。,。∷窃S多分治算法經(jīng)驗的總結(jié),，有助于在分析問題中考慮如何去使用分治算法，提請注意括號里我的注釋?。,。?br>
形象的表示一下,，截張圖：
大多數(shù)都是規(guī)模為n的問題,，被劃分為2個規(guī)模為n/2的問題，更一般的情況下,，從理論上分析一下：
一個規(guī)模為n的實例可以劃分為b個規(guī)模為n/b的實例,，其中a個實例是需要求解的，為了簡化分析,，我們假設(shè)n是b的冪（每次都可以整的劃分）,，對算法的運(yùn)行時間，下面的遞推關(guān)系式是顯然的：
其中,，a,，b的含義已經(jīng)說過了，f（n）表示將求解得到的a個子問題的解合并起來所需要的時間復(fù)雜度,。
如何根據(jù)a,，b以及f的階來確定這個算法的時間復(fù)雜度呢？有下列主定理：（證明參見算法導(dǎo)論）
看起來似乎是有一點(diǎn)復(fù)雜,，證明又比較復(fù)雜,，這樣的式子又不好記?？吹竭@個我也覺得茫然,。好吧，根據(jù)自己的理解,，我來做一點(diǎn)解析,，挖掘一下這個式子：
1）b，a,，f（n）的含義,，這個要弄清楚,，要不然恐怕你是無法記住這個結(jié)論的。
2）這個式子是一個通用的數(shù)學(xué)表達(dá)式,，在計算機(jī)的常用算法策略中,，它太概括了，我們往往用到的只是它范圍很小的一部分,。
分析1：a和b的關(guān)系,，其實a絕大多數(shù)時候都是等于b的吧（因為規(guī)模n劃分為了b個子規(guī)模，需要處理的是a個,，參見a,，b的含義），a,，b的含義告訴我們a <= b（當(dāng)這是最基本要滿足的條件）,。常常要么是 a==b（分成的子規(guī)模都要處理，然后去合并）,，要么是a==1（實際上這是減治的思想,，分成了b個子規(guī)模，但最終卻可以排除其他的,，只在其中一個子規(guī)模中去處理）,。一般來說就是這樣，所以a,，b并不是隨意的,。
分析2：其實b要么為2（幾乎所有情況）要么為3（極少數(shù)情況）吧，這個分治思想里面就說啦,，一般來說都是分為2個規(guī)模相等的子規(guī)模（當(dāng)然誰都想分的越多越好,，這樣算法就更快，但是現(xiàn)實是問題往往沒有那么高效的算法,，找到一個3的分治就已經(jīng)很不錯了）
分析3：由上面2條可知,，a，b的值幾乎就那么幾個（當(dāng)然我說的是幾乎所有書上可以看到的常見算法案例）,，所以不用那么擔(dān)心,。
分析4：f（n）是線性的的情況很多（即d=1的情況是最多的）。再來看看a和b^d比較大小的關(guān)系說明了什么：f（n）代表的是合并的復(fù)雜度,，1<=a <= b,定性的分析,，可以知道：
第一種情況：a < b^d
因為1<=a <= b,所以只要d>1,不管a，b是什么（不管怎么劃分規(guī)模,，也不關(guān)需要處理幾個規(guī)模）,，總是第一種情況，時間復(fù)雜度是n^d,。
如果d=1呢,，只要a < b(處理的比劃分的少),，那么還是第一種情況，時間復(fù)雜度也是n^d = n
第二種情況：a = b^d
因為1<=a <= b,所以如果a=b（劃分多少處理多少）,那么d只能為1才能是這種情況,。-----常見的歸并排序都是這樣
而如果a < b,那b就只能<1才能是這種情況,，一般很少見。
第三種情況：a > b^d
非常少見,，我還木有見過這樣的算法,，一開始我認(rèn)為這種情況不可能，但在理論上它是存在的,。因為1<=a <= b,所以要滿足這個式子d必須<1 ,。
從這也可以看出這三個參數(shù)之間的關(guān)系，事實上是劃分的復(fù)雜度和合并的復(fù)雜度在爭搶復(fù)雜度的控制權(quán),。
說了這么多,，感覺越分析越復(fù)雜了嗎，其實不是,，把這些分析想清楚，對遞推式的理解就更進(jìn)一步了,，有了上述分析,，其實下面幾個常見的遞推式就包含了大多數(shù)的算法：
T(n) = a * T(n/b) + f(n)的常見式子：
1) T(n) = 2 * T(n/2) + O(n) 時間復(fù)雜度n*log(n)
一般來說分治算法就是這樣，分成2個子規(guī)模的問題,，需要處理的也是2個,，對這兩個子規(guī)模合并又是線性的
a = b = 2, d = 1; a == b^d 由主定理得n*log(n)
只要a=b,d=1,就都是這個復(fù)雜度
2) T(n) = T(n/2) + O(n) 時間復(fù)雜度為n，線性的
a = 1,，b = 2,，d=1（分為2個子規(guī)模，但只對一個子規(guī)模處理,，合并也是線性的）
a < b^d, 時間復(fù)雜度是n^d = n
其實質(zhì)押a < b,d=1,都是這個,。
感覺對一個定理解讀了這么多，確實讓它變得更加復(fù)雜了,，但如果你做了上述思考,，相信對這個式子認(rèn)識也更加深刻了一點(diǎn)。當(dāng)然,，如果你覺得直接記住上面這個公式就可以了,，可以無視以上解讀。
----------------------------------------------------------------------------------------------------------------------------------------------------
4.1 合并排序
數(shù)據(jù)結(jié)構(gòu)里面寫過了,，再從分治實現(xiàn)策略的角度想一想：
合并排序遞歸的將規(guī)模n分為2個子規(guī)模,，對2個子規(guī)模分別排好序后（劃分并處理），再來合并這2個子規(guī)模為有序（合并解）,。
其遞推關(guān)系式是這樣的：
合并解的過程是線性的,，即：
由主定理得,，時間復(fù)雜度是n * logn的。
幾道習(xí)題的思考：
7,，合并排序穩(wěn)定嗎,？yes
10，也可以不用遞歸的方法來實現(xiàn)合并排序,，合并排序是采用遞歸從上往下構(gòu)造,，我們也可以合并2個相鄰序列從底向上構(gòu)造。這樣就需要不斷地申請一個大的數(shù)組,，把當(dāng)前相鄰的2個部分合并起來,，直到整個合并。
--------------------------------------------------------------------------------------------------------------------------------------------------
4.2 快速排序
前面數(shù)據(jù)結(jié)構(gòu)里寫過了,，從分治實現(xiàn)策略的解讀來看看：
歸并排序是按照元素在數(shù)組里的位置來對它們進(jìn)行劃分的,，而快速排序是按照元素的值對它們進(jìn)行劃分。
遞推關(guān)系式：
根據(jù)主定理得知,，時間復(fù)雜度和歸并排序一樣,。
1）其關(guān)鍵在于尋找分裂位置！?。,。。?strong>2個指針左右掃描,，交換,。注意這種方法）
2）學(xué)會快排采用的分區(qū)這種思想。
幾道習(xí)題的思考：
3,，快排穩(wěn)定嗎,？ ---- no
8，將一個亂序數(shù)組排成所有負(fù)數(shù)在正數(shù)之前,。-----借用快排2個指針左右掃描交換的思想,，線性時間內(nèi)完成
9，荷蘭國旗問題------分區(qū)思想
---------------------------------------------------------------------------------------------------------------------------------------------------
4.3 折半查找
前面數(shù)據(jù)結(jié)構(gòu)寫過了,，從分治策略的角度看看：
對有序數(shù)組采用折半查找：遞歸和非遞歸實現(xiàn)都比較簡單,。
分治的遞推式：
根據(jù)主定理，它的復(fù)雜度是logn,。
實際上分治算法一般是分成了幾個子規(guī)模就對這幾個子規(guī)模處理然后合并結(jié)果,，然而折半查找分成了2個子規(guī)模，每次卻總能排除一個子規(guī)模,，只對一個子規(guī)模進(jìn)行處理,，準(zhǔn)確的說，它是一種減治策略,?；蛘哒f可以把它看做是分治算法的退化,。
--------------------------------------------------------------------------------------------------------------------------------------------------
4.4 二叉樹遍歷及相關(guān)特性
很多算法也在前面寫過了，還是從分治策略的角度再來看看它的一些特性：
二叉樹的定義本身（參見一般的數(shù)據(jù)結(jié)構(gòu)書）,，把一顆二叉樹遞歸的定義為了左右子樹構(gòu)成的樹,。這意味著，分治法是典型可以用于解決二叉樹相關(guān)問題的策略,。
來看看可以做些什么：
1）計算二叉樹的高度
注意初始條件是判斷是否為空集返回一個 -1,，后面有一個習(xí)題說是否可以寫成返回0，然后else里面不加1,。這是不行的?。∵@樣沒有考慮單節(jié)點(diǎn)的情況,。
它的遞推關(guān)系式：
你能由這個遞歸關(guān)系給出它的時間復(fù)雜度嗎,？想想~
事實上，可以簡化它為A（n） = 2 * A(n / 2) + 1 -------把左右的處理當(dāng)做一個數(shù)量級,，不會影響復(fù)雜度,，根據(jù)主定理，它是O(n)的,。
來看看怎么證明它吧----》
參見第 2）點(diǎn)
2）應(yīng)當(dāng)指出,，加法并不是上述算法中執(zhí)行最多的次數(shù)，每得到一個左子樹和右子樹,，才執(zhí)行一次加法（先求max，再執(zhí)行+1）,，而比較次數(shù)（指檢查樹是否為空,，即if語句）顯然不止一次（要判斷根節(jié)點(diǎn)是否為空，還要判斷左右子樹是否為空）,。
這里引入內(nèi)部節(jié)點(diǎn)和外部結(jié)點(diǎn)的概念（定義略）來分析問題?。。,。?br>
顯然對于每個內(nèi)部節(jié)點(diǎn)都要計算一次加法,，對于內(nèi)部節(jié)點(diǎn)和外部結(jié)點(diǎn)，都要執(zhí)行一次比較（判斷是否為空）,。
可以證明,，有n個結(jié)點(diǎn)的二叉樹的外部結(jié)點(diǎn)個數(shù)為 x = n + 1；（如上圖,，用數(shù)學(xué)歸納法或者圖論相關(guān)知識都很好證明,，證明略）
根據(jù)上述分析，對一個n個頂點(diǎn)的二叉樹求高度,，
加法的操作次數(shù)為內(nèi)頂點(diǎn)個數(shù)：n
比較判斷是否為空的操作次數(shù)為內(nèi)部點(diǎn)加外部點(diǎn)的個數(shù)：n + （n + 1） = 2n + 1,；
無論怎么說,，該算法是線性的！
3）其他一些如三種經(jīng)典的遍歷算法,，都可以遞歸的來定義,，這些都是數(shù)據(jù)結(jié)構(gòu)課程的標(biāo)準(zhǔn)組成部分，前面已寫,，不再詳述,。
最后指出一點(diǎn)，并不是所有的二叉樹算法都要遍歷左右子樹,，例如二叉查找樹的插入查找刪除只需要遍歷一棵（每次總能排除一棵）,，這種策略應(yīng)該歸于減可變規(guī)模的策略（參見下一章減治策略）。
幾道習(xí)題的思考：
1）設(shè)計一個分治算法來計算二叉樹的層數(shù),。-----------遞歸的返回左右子樹層數(shù)較大值+1,，注意空樹和單節(jié)點(diǎn)時的情況
最后，擴(kuò)展一下本節(jié)最開始的計算二叉樹高度的算法：
一道騰訊面試題：怎么求二叉樹上最遠(yuǎn)的2個節(jié)點(diǎn)的距離,？-------左子樹高度+右子樹高度+2,，注意特殊情況（只有一邊右子樹）就行了。
--------------------------------------------------------------------------------------------------------------------------------------------------
總結(jié)：
1）分治的思想：一般遞歸來實現(xiàn),，劃分子問題,，合并子問題的解。
2）主定理,，要很熟悉,，常見的遞推式應(yīng)該一眼判斷其復(fù)雜度。
3）合并排序,，快速排序,，折半查找，二叉遍歷樹相關(guān)特性,，這些都是數(shù)據(jù)結(jié)構(gòu)的經(jīng)典內(nèi)容,，之前也都寫過了，代碼參見前面的相關(guān)文章,。
這里再次復(fù)習(xí),，從不同的視角來看它們都是如何用用到了分治的策略。這些內(nèi)容應(yīng)當(dāng)非常熟練,。
|
