分治算法基本思想和典型例題
1 算法思想
分而治之方法與軟體設計的子產品化方法非常相似。為了解決一個大的問題，可以： 1) 把它分成兩個或多個更小的問題； 2) 分别解決每個小問題； 3) 把各小問題的解答組合起來，即可得到原問題的解答。小問題通常與原問題相似，可以遞歸地使用分而治之政策來解決。
例1 [找出僞币] 給你一個裝有1 6個硬币的袋子。1 6個硬币中有一個是僞造的，并且那個僞造的硬币比真的硬币要輕一些。你的任務是找出這個僞造的硬币。為了幫助你完成這一任務，将提供一台可用來比較兩組硬币重量的儀器，利用這台儀器，可以知道兩組硬币的重量是否相同。比較硬币1與硬币2的重量。假如硬币1比硬币2輕，則硬币1是僞造的；假如硬币2比硬币1輕，則硬币2是僞造的。這樣就完成了任務。假如兩硬币重量相等，則比較硬币3和硬币4。同樣，假如有一個硬币輕一些，則尋找僞币的任務完成。假如兩硬币重量相等，則繼續比較硬币5和硬币6。按照這種方式，可以最多通過8次比較來判斷僞币的存在并找出這一僞币。
另外一種方法就是利用分而治之方法。假如把1 6硬币的例子看成一個大的問題。第一步，把這一問題分成兩個小問題。随機選擇8個硬币作為第一組稱為A組，剩下的8個硬币作為第二組稱為B組。這樣，就把1 6個硬币的問題分成兩個8硬币的問題來解決。第二步，判斷A和B組中是否有僞币。可以利用儀器來比較A組硬币和B組硬币的重量。假如兩組硬币重量相等，則可以判斷僞币不存在。假如兩組硬币重量不相等，則存在僞币，并且可以判斷它位于較輕的那一組硬币中。最後，在第三步中，用第二步的結果得出原先1 6個硬币問題的答案。若僅僅判斷硬币是否存在，則第三步非常簡單。無論A組還是B組中有僞币，都可以推斷這1 6個硬币中存在僞币。是以，僅僅通過一次重量的比較，就可以判斷僞币是否存在。
現在假設需要識别出這一僞币。把兩個或三個硬币的情況作為不可再分的小問題。注意如果隻有一個硬币，那麼不能判斷出它是否就是僞币。在一個小問題中，通過将一個硬币分别與其他兩個硬币比較，最多比較兩次就可以找到僞币。這樣，1 6硬币的問題就被分為兩個8硬币（A組和B組）的問題。通過比較這兩組硬币的重量，可以判斷僞币是否存在。如果沒有僞币，則算法終止。否則，繼續劃分這兩組硬币來尋找僞币。假設B是輕的那一組，是以再把它分成兩組，每組有4個硬币。稱其中一組為B1，另一組為B2。比較這兩組，肯定有一組輕一些。如果B1輕，則僞币在B1中，再将B1又分成兩組，每組有兩個硬币，稱其中一組為B1a，另一組為B1b。比較這兩組，可以得到一個較輕的組。由于這個組隻有兩個硬币，是以不必再細分。比較組中兩個硬币的重量，可以立即知道哪一個硬币輕一些。較輕的硬币就是所要找的僞币。
例2 [金塊問題] 有一個老闆有一袋金塊。每個月将有兩名雇員會因其優異的表現分别被獎勵一個金塊。按規矩，排名第一的雇員将得到袋中最重的金塊，排名第二的雇員将得到袋中最輕的金塊。根據這種方式，除非有新的金塊加入袋中，否則第一名雇員所得到的金塊總是比第二名雇員所得到的金塊重。如果有新的金塊周期性的加入袋中，則每個月都必須找出最輕和最重的金塊。假設有一台比較重量的儀器，我們希望用最少的比較次數找出最輕和最重的金塊。
假設袋中有n 個金塊。可以用函數M a x（程式1 - 3 1）通過n-1次比較找到最重的金塊。找到最重的金塊後，可以從餘下的n-1個金塊中用類似的方法通過n-2次比較找出最輕的金塊。這樣，比較的總次數為2n-3。程式2 - 2 6和2 - 2 7是另外兩種方法，前者需要進行2n-2次比較，後者最多需要進行2n-2次比較。
下面用分而治之方法對這個問題進行求解。當n很小時，比如說， n≤2，識别出最重和最輕的金塊，一次比較就足夠了。當n 較大時（n＞2），第一步，把這袋金塊平分成兩個小袋A和B。第二步，分别找出在A和B中最重和最輕的金塊。設A中最重和最輕的金塊分别為HA 與LA，以此類推，B中最重和最輕的金塊分别為HB 和LB。第三步，通過比較HA 和HB，可以找到所有金塊中最重的；通過比較LA 和LB，可以找到所有金塊中最輕的。在第二步中，若n＞2，則遞歸地應用分而治之方法。
假設n= 8。這個袋子被平分為各有4個金塊的兩個袋子A和B。為了在A中找出最重和最輕的金塊，A中的4個金塊被分成兩組A1和A2。每一組有兩個金塊，可以用一次比較在A中找出較重的金塊HA1和較輕的金塊LA1。經過另外一次比較，又能找出HA 2和LA 2。現在通過比較HA1和HA2，能找出HA；通過LA 1和LA2的比較找出LA。這樣，通過4次比較可以找到HA 和LA。同樣需要另外4次比較來确定HB 和LB。通過比較HA 和HB（LA 和LB），就能找出所有金塊中最重和最輕的。是以，當n= 8時，這種分而治之的方法需要1 0次比較。如果使用程式1 - 3 1，則需要1 3次比較。如果使用程式2 - 2 6和2 - 2 7，則最多需要1 4次比較。設c(n)為使用分而治之方法所需要的比較次數。為了簡便，假設n是2的幂。當n= 2時，c(n) = 1。對于較大的n，c(n) = 2c(n/ 2 ) + 2。當n是2的幂時，使用疊代方法（見例2 - 2 0）可知 c(n) = 3n/ 2 - 2。在本例中，使用分而治之方法比逐個比較的方法少用了2 5％的比較次數。
例3 [矩陣乘法] 兩個n×n 階的矩陣A與B的乘積是另一個n×n 階矩陣C，C可表示為假如每一個C(i, j) 都用此公式計算，則計算C所需要的操作次數為n3 m+n2 (n- 1) a，其中m表示一次乘法，a 表示一次加法或減法。
為了得到兩個矩陣相乘的分而治之算法，需要： 1) 定義一個小問題，并指明小問題是如何進行乘法運算的； 2) 确定如何把一個大的問題劃分成較小的問題，并指明如何對這些較小的問題進行乘法運算； 3) 最後指出如何根據小問題的結果得到大問題的結果。為了使讨論簡便，假設n 是2的幂（也就是說， n是1，2，4，8，1 6，.）。
首先，假設n= 1時是一個小問題，n> 1時為一個大問題。後面将根據需要随時修改這個假設。對于1×1階的小矩陣，可以通過将兩矩陣中的兩個元素直接相乘而得到結果。
考察一個n> 1的大問題。可以将這樣的矩陣分成4個n/ 2×n/ 2階的矩陣A1，A2，A3，和A4。當n 大于1且n 是2的幂時，n/ 2也是2的幂。是以較小矩陣也滿足前面對矩陣大小的假設。矩陣Bi 和Ci 的定義與此類似.
根據上述公式，經過8次n/ 2×n/ 2階矩陣乘法和4次n/ 2×n/ 2階矩陣的加法，就可以計算出A與B的乘積。是以，這些公式能幫助我們實作分而治之算法。在算法的第二步，将遞歸使用分而治之算法把8個小矩陣再細分（見程式2 - 1 9）。算法的複雜性為(n3 )，此複雜性與程式2 - 2 4直接使用公式（2 - 1）所得到的複雜性是一樣的。事實上，由于矩陣分割和再組合所花費的額外開銷，使用分而治之算法得出結果的時間将比用程式2 - 2 4還要長。
為了得到更快的算法，需要簡化矩陣分割和再組合這兩個步驟。一種方案是使用S t r a s s e n方法得到7個小矩陣。這7個小矩陣為矩陣D, E, ., J，矩陣D到J可以通過7次矩陣乘法， 6次矩陣加法，和4次矩陣減法計算得出。前述的4個小矩陣可以由矩陣D到J通過6次矩陣加法和兩次矩陣減法得出.
用上述方案來解決n= 2的矩陣乘法。将某矩陣A和B相乘得結果C，如下所示：
因為n> 1，是以将A、B兩矩陣分别劃分為4個小矩陣，每個矩陣為1×1階，僅包含一個元素。1×1階矩陣的乘法為小問題，是以可以直接進行運算。利用計算D～J的公式，得：
D= 1（6-8）=-2
E= 4（7-5）= 8
F=（3 + 4）5 = 3 5
G=（1 + 2）8 = 2 4
H=（3-1）（5 + 6）= 2 2
I=（2-4）（7 + 8）=-3 0
J=（1 + 4）（5 + 8）= 6 5
根據以上結果可得：
對于上面這個2×2的例子，使用分而治之算法需要7次乘法和1 8次加/減法運算。而直接使用公式（2 - 1），則需要8次乘法和7次加/減法。要想使分而治之算法更快一些，則一次乘法所花費的時間必須比11次加/減法的時間要長。
假定S t r a s s e n矩陣分割方案僅用于n≥8的矩陣乘法，而對于n<8的矩陣乘法則直接利用公式（2 - 1）進行計算。則n= 8時，8×8矩陣相乘需要7次4×4矩陣乘法和1 8次4×4矩陣加/減法。每次矩陣乘法需花費6 4m+ 4 8a次操作，每次矩陣加法或減法需花費1 6a次操作。是以總的操作次數為7 ( 6 4m+ 4 8a) + 1 8 ( 1 6a) = 4 4 8m+ 6 2 4a。而使用直接計算方法，則需要5 1 2m+ 4 4 8a次操作。要使S t r a s s e n方法比直接計算方法快，至少要求5 1 2-4 4 8次乘法的開銷比6 2 4-4 4 8次加/減法的開銷大。或者說一次乘法的開銷應該大于近似2 . 7 5次加/減法的開銷。
假定n<1 6的矩陣是一個“小”問題，S t r a s s e n的分解方案僅僅用于n≥1 6的情況，對于n<1 6的矩陣相乘，直接利用公式（ 2 - 1）。則當n= 1 6時使用分而治之算法需要7 ( 5 1 2m+ 4 4 8a) +1 8 ( 6 4a) = 3 5 8 4m+ 4 2 8 8a次操作。直接計算時需要4 0 9 6m+ 3 8 4 0a次操作。若一次乘法的開銷與一次加/減法的開銷相同，則S t r a s s e n方法需要7 8 7 2次操作及用于問題分解的額外時間，而直接計算方法則需要7 9 3 6次操作加上程式中執行f o r循環以及其他語句所花費的時間。即使直接計算方法所需要的操作次數比St r a s s e n方法少，但由于直接計算方法需要更多的額外開銷，是以它也不見得會比S t r a s s e n方法快。
n 的值越大，Strassen 方法與直接計算方法所用的操作次數的差異就越大，是以對于足夠大的n，Strassen 方法将更快。設t (n) 表示使用Strassen 分而治之方法所需的時間。因為大的矩陣會被遞歸地分割成小矩陣直到每個矩陣的大小小于或等于k（k至少為8，也許更大，具體值由計算機的性能決定）. 用疊代方法計算，可得t(n) = (nl og27 )。因為l og27 ≈2 . 8 1，是以與直接計算方法的複雜性(n3 )相比，分而治之矩陣乘法算法有較大的改進。
注意事項
分而治之方法很自然地導緻了遞歸算法的使用。在許多例子裡，這些遞歸算法在遞歸程式中得到了很好的運用。實際上，在許多情況下，所有為了得到一個非遞歸程式的企圖都會導緻采用一個模拟遞歸棧。不過在有些情況下，不使用這樣的遞歸棧而采用一個非遞歸程式來完成分而治之算法也是可能的，并且在這種方式下，程式得到結果的速度會比遞歸方式更快。解決金塊問題的分而治之算法（例2 - 2）和歸并排序方法（ 2 . 3節）就可以不利用遞歸而通過一個非遞歸程式來更快地完成。
例4 [金塊問題] 用例2 - 2的算法尋找8個金塊中最輕和最重金塊的工作可以用二叉樹來表示。這棵樹的葉子分别表示8個金塊（a, b,., h)，每個陰影節點表示一個包含其子樹中所有葉子的問題。是以，根節點A表示尋找8個金塊中最輕、最重金塊的問題，而節點B表示找出a,b,c 和d 這4個金塊中最輕和最重金塊的問題。算法從根節點開始。由根節點表示的8金塊問題被劃分成由節點B和C所表示的兩個4金塊問題。在B節點，4金塊問題被劃分成由D和E所表示的2金塊問題。可通過比較金塊a 和b 哪一個較重來解決D節點所表示的2金塊問題。在解決了D和E所表示的問題之後，可以通過比較D和E中所找到的輕金塊和重金塊來解決B表示的問題。接着在F，G和C上重複這一過程，最後解決問題A。
可以将遞歸的分而治之算法劃分成以下的步驟：
1) 從圖2 - 2中的二叉樹由根至葉的過程中把一個大問題劃分成許多個小問題，小問題的大小為1或2。
2) 比較每個大小為2的問題中的金塊，确定哪一個較重和哪一個較輕。在節點D、E、F和G上完成這種比較。大小為1的問題中隻有一個金塊，它既是最輕的金塊也是最重的金塊。
3) 對較輕的金塊進行比較以确定哪一個金塊最輕，對較重的金塊進行比較以确定哪一個金塊最重。對于節點A到C執行這種比較。
根據上述步驟，可以得出程式1 4 - 1的非遞歸代碼。該程式用于尋找到數組w [ 0 : n - 1 ]中的最小數和最大數，若n < 1，則程式傳回f a l s e，否則傳回t r u e。
當n≥1時，程式1 4 - 1給M i n和M a x置初值以使w [ M i n ]是最小的重量，w [ M a x ]為最大的重量。
首先處理n≤1的情況。若n>1且為奇數，第一個重量w [ 0 ]将成為最小值和最大值的候選值，是以将有偶數個重量值w [ 1 : n - 1 ]參與f o r循環。當n 是偶數時，首先将兩個重量值放在for 循環外進行比較，較小和較大的重量值分别置為Min和Max，是以也有偶數個重量值w[2:n-1]參與for循環。
在for 循環中，外層if 通過比較确定( w [ i ] , w [ i + 1 ] )中的較大和較小者。此工作與前面提到的分而治之算法步驟中的2) 相對應，而内層的i f負責找出較小重量值和較大重量值中的最小值和最大值，這個工作對應于3 )。for 循環将每一對重量值中較小值和較大值分别與目前的最小值w [ M i n ]和最大值w [ M a x ]進行比較，根據比較結果來修改M i n和M a x（如果必要）。
下面進行複雜性分析。注意到當n為偶數時，在for 循環外部将執行一次比較而在f o r循環内部執行3 ( n / 2 - 1 )次比較，比較的總次數為3 n / 2 - 2。當n 為奇數時，f o r循環外部沒有執行比較，而内部執行了3(n-1)/2次比較。是以無論n 為奇數或偶數，當n>0時，比較的總次數為「3n/2ù-2次。
程式14-1 找出最小值和最大值的非遞歸程式
template<class T>
bool MinMax(T w[], int n, T& Min, T& Max)
{// 尋找w [ 0 : n - 1 ]中的最小和最大值
// 如果少于一個元素，則傳回f a l s e
// 特殊情形： n <= 1
if (n < 1) return false;
if (n == 1) {Min = Max = 0;
return true;}
/ /對Min 和M a x進行初始化
int s; // 循環起點
if (n % 2) {// n 為奇數
Min = Max = 0;
s = 1;}
else {// n為偶數，比較第一對
if (w[0] > w[1]) {
Min = 1;
Max = 0;}
else {Min = 0;
Max = 1;}
s = 2;}
// 比較餘下的數對
for (int i = s; i < n; i += 2) {
// 尋找w[i] 和w [ i + 1 ]中的較大者
// 然後将較大者與w [ M a x ]進行比較
// 将較小者與w [ M i n ]進行比較
if (w[i] > w[i+1]) {
if (w[i] > w[Max]) Max = i;
if (w[i+1] < w[Min]) Min = i + 1;}
else {
if (w[i+1] > w[Max]) Max = i + 1;
if (w[i] < w[Min]) Min = i;}
}
return true;
}
練習
1. 将例1 4 - 1的分而治之算法擴充到n> 1個硬币的情形。需要進行多少次重量的比較？
2. 考慮例1 4 - 1的僞币問題。假設把條件“僞币比真币輕”改為“僞币與真币的重量不同”，同樣假定袋中有n 個硬币。
1) 給出相應分而治之算法的形式化描述，該算法可輸出資訊“不存在僞币”或找出僞币。算法應遞歸地将大的問題劃分成兩個較小的問題。需要多少次比較才能找到僞币（如果存在僞币）？
2) 重複1) ，但把大問題劃分為三個較小問題。
3. 1) 編寫一個C++ 程式，實作例1 4 - 2中尋找n 個元素中最大值和最小值的兩種方案。使用遞歸來完成分而治之方案。
2) 程式2 - 2 6和2 - 2 7是另外兩個尋找n 個元素中最大值和最小值的代碼。試分别計算出每段程式所需要的最少和最大比較次數。
3) 在n 分别等于1 0 0，1 0 0 0或10 000的情況下，比較1）、2）中的程式和程式1 4 - 1的運作時間。對于程式2 - 2 7，使用平均時間和最壞情況下的時間。1）中的程式和程式2 - 2 6應具有相同的平均時間和最壞情況下的時間。
4) 注意到如果比較操作的開銷不是很高，分而治之算法在最壞情況下不會比其他算法優越，為什麼？它的平均時間優于程式2 - 2 7嗎？為什麼？
4. 證明直接運用公式（1 4 -2）~（1 4 - 5）得出結果的矩陣乘法的分而治之算法的複雜性為(n3 )。是以相應的分而治之程式将比程式2 - 2 4要慢。
5. 用疊代的方法來證明公式（1 4 - 6）的遞歸值為(n l og27)。
*6. 編寫S t r a s s e n矩陣乘法程式。利用不同的k 值（見公式（1 4 - 6））進行實驗，以确定k 為何值時程式性能最佳。比較程式及程式2 - 2 4的運作時間。可取n 為2的幂來進行比較。
7. 當n 不是2的幂時，可以通過增加矩陣的行和列來得到一個大小為2的幂的矩陣。假設使用最少的行數和列數将矩陣擴充為m 階矩陣，其中m 為2的幂。
1) 求m / n。
2) 可使用哪些矩陣項組成新的行和列，以使新矩陣A 和B 相乘時，原來的矩陣A和B相乘的結果會出現在C 的左上角？
3) 使用S t r a s s e n方法計算A * B 所需要的時間為(m2.81 )。給出以n 為變量的運作時間表達式。