分而治之算法論述-全文預(yù)覽
【正文】 式下，程序得到結(jié)果的速度會(huì)比遞歸方式更快。注意事項(xiàng)n 的值越大，Strassen 方法與直接計(jì)算方法所用的操作次數(shù)的差異就越大，因此對(duì)于足夠大的n，Strassen 方法將更快。則當(dāng)n= 1 6時(shí)使用分而治之算法需要7 ( 5 1 2m+ 4 4 8a) +1 8 ( 6 4a) = 3 5 8 4m+ 4 2 8 8a次操作。而使用直接計(jì)算方法，則需要5 1 2m+ 4 4 8a次操作。假定S t r a s s e n矩陣分割方案僅用于n≥8的矩陣乘法，而對(duì)于n8的矩陣乘法則直接利用公式（2 1）進(jìn)行計(jì)算。11階矩陣的乘法為小問題，因此可以直接進(jìn)行運(yùn)算。一種方案是使用S t r a s s e n方法得到7個(gè)小矩陣。在算法的第二步，將遞歸使用分而治之算法把8個(gè)小矩陣再細(xì)分（見程序2 1 9）。當(dāng)n 大于1且n 是2的冪時(shí)，n/ 2也是2的冪。后面將根據(jù)需要隨時(shí)修改這個(gè)假設(shè)。例23 [矩陣乘法] 兩個(gè)nn 階的矩陣A與B的乘積是另一個(gè)nn 階矩陣C，C可表示為假如每一個(gè)C(i, j) 都用此公式計(jì)算，則計(jì)算C所需要的操作次數(shù)為n3 m+n2 (n 1) a，其中m表示一次乘法，a 表示一次加法或減法。當(dāng)n= 2時(shí)，c(n) = 1。如果使用程序1 3 1，則需要1 3次比較。這樣，通過4次比較可以找到HA 和LA。為了在A中找出最重和最輕的金塊，A中的4個(gè)金塊被分成兩組A1和A2。第三步，通過比較HA 和HB，可以找到所有金塊中最重的；通過比較LA 和LB，可以找到所有金塊中最輕的。當(dāng)n很小時(shí)，比如說， n≤2，識(shí)別出最重和最輕的金塊，一次比較就足夠了。找到最重的金塊后，可以從余下的n1個(gè)金塊中用類似的方法通過n2次比較找出最輕的金塊。如果有新的金塊周期性的加入袋中，則每個(gè)月都必須找出最輕和最重的金塊。例22 [金塊問題] 有一個(gè)老板有一袋金塊。比較這兩組，可以得到一個(gè)較輕的組。假設(shè)B是輕的那一組，因此再把它分成兩組，每組有4個(gè)硬幣。這樣，1 6硬幣的問題就被分為兩個(gè)8硬幣（A組和B組）的問題。現(xiàn)在假設(shè)需要識(shí)別出這一偽幣。最后，在第三步中，用第二步的結(jié)果得出原先1 6個(gè)硬幣問題的答案。第二步，判斷A和B組中是否有偽幣。假如把1 6硬幣的例子看成一個(gè)大的問題。同樣，假如有一個(gè)硬幣輕一些，則尋找偽幣的任務(wù)完成。比較硬幣1與硬幣2的重量。例21 [找出偽幣] 給你一個(gè)裝有1 6個(gè)硬幣的袋子。 本章給出了用來分析分而治之算法復(fù)雜性的數(shù)學(xué)方法，并通過推導(dǎo)最小最大問題和排序問題的復(fù)雜性下限來證明分而治之算法對(duì)于求解這兩種問題是最優(yōu)的（因?yàn)樗惴ǖ膹?fù)雜性與下限一致）。本章將首先介紹怎樣在算法設(shè)計(jì)領(lǐng)域應(yīng)用這一古老的策略，然后將利用這一策略解決如下問題：最小最大問題、矩陣乘法、殘缺棋盤、排序、選擇和計(jì)算一個(gè)幾何問題——找出二維空間中距離最近的兩個(gè)點(diǎn)。小問題通常與原問題相似，可以遞歸地使用分而治之策略來解決。為了幫助你完成這一任務(wù)，將提供一臺(tái)可用來比較兩組硬幣重量的儀器，利用這臺(tái)儀器，可以知道兩組硬幣的重量是否相同。假如兩硬幣重量相等，則比較硬幣3和硬幣4。另外一種方法就是利用分而治之方法。這樣，就把1 6個(gè)硬幣的問題分成兩個(gè)8硬幣的問題來解決。假如兩組硬幣重量不相等，則存在偽幣，并且可以判斷它位于較輕的那一組硬幣中。因此，僅僅通過一次重量的比較，就可以判斷偽幣是否存在。在一個(gè)小問題中，通過將一個(gè)硬幣分別與其他兩個(gè)硬幣比較，最多比較兩次就可以找到偽幣。否則，繼續(xù)劃分這兩組硬幣來尋找偽幣。如果B1輕，則偽幣在B1中，再將B1又分成兩組，每組有兩個(gè)硬幣，稱其中一組為B1a，另一組為B1b。較輕的硬幣就是所要找的偽幣。根據(jù)這種方式，除非有新的金塊加入
環(huán)評(píng)公示相關(guān)推薦
鄂ICP備17016276號(hào)-1