分而治之算法論述-文庫吧
2025-07-20 14:25 本頁面
【正文】 假設(shè)袋中有n 個金塊?？梢杂煤瘮?shù)M a x（程序1 3 1）通過n1次比較找到最重的金塊。找到最重的金塊后，可以從余下的n1個金塊中用類似的方法通過n2次比較找出最輕的金塊。這樣，比較的總次數(shù)為2n3。程序2 2 6和2 2 7是另外兩種方法，前者需要進行2n2次比較，后者最多需要進行2n2次比較。下面用分而治之方法對這個問題進行求解。當(dāng)n很小時，比如說， n≤2，識別出最重和最輕的金塊，一次比較就足夠了。當(dāng)n 較大時（n＞2），第一步，把這袋金塊平分成兩個小袋A和B。第二步，分別找出在A和B中最重和最輕的金塊。設(shè)A中最重和最輕的金塊分別為HA 與LA，以此類推，B中最重和最輕的金塊分別為HB 和LB。第三步，通過比較HA 和HB，可以找到所有金塊中最重的；通過比較LA 和LB，可以找到所有金塊中最輕的。在第二步中，若n＞2，則遞歸地應(yīng)用分而治之方法。假設(shè)n= 8。這個袋子被平分為各有4個金塊的兩個袋子A和B。為了在A中找出最重和最輕的金塊，A中的4個金塊被分成兩組A1和A2。每一組有兩個金塊，可以用一次比較在A中找出較重的金塊HA1和較輕的金塊LA1。經(jīng)過另外一次比較，又能找出HA 2和LA 2?，F(xiàn)在通過比較HA1和HA2，能找出HA；通過LA 1和LA2的比較找出LA。這樣，通過4次比較可以找到HA 和LA。同樣需要另外4次比較來確定HB 和LB。通過比較HA 和HB（LA 和LB），就能找出所有金塊中最重和最輕的。因此，當(dāng)n= 8時，這種分而治之的方法需要1 0次比較。如果使用程序1 3 1，則需要1 3次比較。如果使用程序2 2 6和2 2 7，則最多需要1 4次比較。設(shè)c(n)為使用分而治之方法所需要的比較次數(shù)。為了簡便，假設(shè)n是2的冪。當(dāng)n= 2時，c(n) = 1。對于較大的n，c(n) = 2c(n/ 2 ) + 2。當(dāng)n是2的冪時，使用迭代方法（見例2 2 0）可知c(n) = 3n/ 2 2。在本例中，使用分而治之方法比逐個比較的方法少用了2 5％的比較次數(shù)。例23 [矩陣乘法] 兩個nn 階的矩陣A與B的乘積是另一個nn 階矩陣C，C可表示為假如每一個C(i, j) 都用此公式計算，則計算C所需要的操作次數(shù)為n3 m+n2 (n 1) a，其中m表示一次乘法，a 表示一次加法或減法。為了得到兩個矩陣相乘的分而治之算法，需要： 1) 定義一個小問題，并指明小問題是如何進行乘法運算的； 2) 確定如何把一個大的問題劃分成較小的問題，并指明如何對這些較小的問題進行乘法運算； 3) 最后指出如何根據(jù)小問題的結(jié)果得到大問題的結(jié)果。為了使討論簡便，假設(shè)n 是2的冪（也就是說， n是1，2，4，8，1 6，.）。首先，假設(shè)n= 1時是一個小問題，n 1時為一個大問題。后面將根據(jù)需要隨時修改這個假設(shè)。對于11階的小矩陣，可以通過將兩矩陣中的兩個元素直接相乘而得到結(jié)果?？疾煲粋€n 1的大問題?？梢詫⑦@樣的矩陣分成4個n/ 2n/ 2階的矩陣A1，A2，A3，和A4。當(dāng)n 大于1且n 是2的冪時，n/ 2也是2的冪。因此較小矩陣也滿足前面對矩陣大小的假設(shè)。矩陣Bi 和Ci 的定義與此類似.根據(jù)上述公式，經(jīng)過8次n/ 2n/ 2階矩陣乘法和4次n/ 2n/ 2階矩陣的加法，就可以計算出A與B的乘積。因此，這些公式能幫助我們實現(xiàn)分而治之算法。在算法的第二步，將遞歸使用分而治之算法把8個小矩陣再細(xì)分（見程序2 1 9）。算法的復(fù)雜性為(n3 )，此復(fù)雜性與程序2 2 4直接使用公式（2 1）所得到的復(fù)雜性是一樣的。事實上，由于矩陣分割和再組合所花費的額外開銷，使用分而治之算法得出結(jié)果的時間將比用程序2
環(huán)評公示相關(guān)推薦
鄂ICP備17016276號-1