君主和殖民者們所成功運用的分而治之策略也可以運用到高效率的計算機算法的設計過程中。本章將首先介紹怎樣在算法設計領域應用這一古老的策略，然後將利用這一策略解決如下問題：最小最大問題、矩陣乘法、殘缺棋盤、排序、選擇和計算一個幾何問題——找出二維空間中距離最近的兩個點。
本章給出了用來分析分而治之算法復雜性的數學方法，並通過推導最小最大問題和排序問題的復雜性下限來證明分而治之算法對於求解這兩種問題是最優的（因為算法的復雜性與下限一致）。
2.1 算法思想
分而治之方法與軟件設計的模塊化方法非常相似。為了解決一個大的問題，可以：1)把它分成兩個或多個更小的問題； 2)分別解決每個小問題； 3)把各小問題的解答組合起來，即可得到原問題的解答。小問題通常與原問題相似，可以遞歸地使用分而治之策略來解決。
例2-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-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％的比較次數。
例2-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節）就可以不利用遞歸而通過一個非遞歸程序來更快地完成。
例2-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
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為變量的運行時間表達式。
