分而治之算法論述-免費閱讀
【正文】 * B39?？扇 為2的冪來進行比較。對于程序2 2 7，使用平均時間和最壞情況下的時間。1) 給出相應分而治之算法的形式化描述，該算法可輸出信息“不存在偽幣”或找出偽幣。if (w[i+1] w[Min]) Min = i + 1。}else {// n為偶數(shù)，比較第一對if (w[0] w[1]) {Min = 1。程序141 找出最小值和最大值的非遞歸程序templatebool MinMax(T w[], int n, Tamp。在for 循環(huán)中，外層if 通過比較確定( w [ i ] , w [ i + 1 ] )中的較大和較小者。3) 對較輕的金塊進行比較以確定哪一個金塊最輕，對較重的金塊進行比較以確定哪一個金塊最重。在B節(jié)點，4金塊問題被劃分成由D和E所表示的2金塊問題。實際上，在許多情況下，所有為了得到一個非遞歸程序的企圖都會導致采用一個模擬遞歸棧。即使直接計算方法所需要的操作次數(shù)比St r a s s e n方法少，但由于直接計算方法需要更多的額外開銷，因此它也不見得會比S t r a s s e n方法快。因此總的操作次數(shù)為7 ( 6 4m+ 4 8a) + 1 8 ( 1 6a) = 4 4 8m+ 6 2 4a。將某矩陣A和B相乘得結果C，如下所示：因為n 1，所以將A、B兩矩陣分別劃分為4個小矩陣，每個矩陣為11階，僅包含一個元素。因此，這些公式能幫助我們實現(xiàn)分而治之算法。首先，假設n= 1時是一個小問題，n 1時為一個大問題。為了簡便，假設n是2的冪。現(xiàn)在通過比較HA1和HA2，能找出HA；通過LA 1和LA2的比較找出LA。設A中最重和最輕的金塊分別為HA 與LA，以此類推，B中最重和最輕的金塊分別為HB 和LB。可以用函數(shù)M a x（程序1 3 1）通過n1次比較找到最重的金塊。較輕的硬幣就是所要找的偽幣。否則，繼續(xù)劃分這兩組硬幣來尋找偽幣。因此，僅僅通過一次重量的比較，就可以判斷偽幣是否存在。這樣，就把1 6個硬幣的問題分成兩個8硬幣的問題來解決。假如兩硬幣重量相等，則比較硬幣3和硬幣4。小問題通常與原問題相似，可以遞歸地使用分而治之策略來解決。 本章給出了用來分析分而治之算法復雜性的數(shù)學方法，并通過推導最小最大問題和排序問題的復雜性下限來證明分而治之算法對于求解這兩種問題是最優(yōu)的（因為算法的復雜性與下限一致）。比較硬幣1與硬幣2的重量。假如把1 6硬幣的例子看成一個大的問題。最后，在第三步中，用第二步的結果得出原先1 6個硬幣問題的答案。這樣，1 6硬幣的問題就被分為兩個8硬幣（A組和B組）的問題。比較這兩組，可以得到一個較輕的組。如果有新的金塊周期性的加入袋中，則每個月都必須找出最輕和最重的金塊。當n很小時，比如說， n≤2，識別出最重和最輕的金塊，一次比較就足夠了。為了在A中找出最重和最輕的金塊，A中的4個金塊被分成兩組A1和A2。如果使用程序1 3 1，則需要1 3次比較。例23 [矩陣乘法] 兩個nn 階的矩陣A與B的乘積是另一個nn 階矩陣C，C可表示為假如每一個C(i, j) 都用此公式計算，則計算C所需要的操作次數(shù)為n3 m+n2 (n 1) a，其中m表示一次乘法，a 表示一次加法或減法。當n 大于1且n 是2的冪時，n/ 2也是2的冪。一種方案是使用S t r a s s e n方法得到7個小矩陣。假定S t r a s s e n矩陣分割方案僅用于n≥8的矩陣乘法，而對于n8的矩陣乘法則直接利用公式（2 1）進行計算。則當n= 1 6時使用分而治之算法需要7 ( 5 1 2m+ 4 4 8a) +1 8 ( 6 4a) = 3 5 8 4m
環(huán)評公示相關推薦
鄂ICP備17016276號-1