分而治之算法論述(編輯修改稿)
2024-08-31 14:25 本頁(yè)面
【文章內(nèi)容簡(jiǎn)介】 2 4還要長(zhǎng)。為了得到更快的算法，需要簡(jiǎn)化矩陣分割和再組合這兩個(gè)步驟。一種方案是使用S t r a s s e n方法得到7個(gè)小矩陣。這7個(gè)小矩陣為矩陣D, E, ., J，矩陣D到J可以通過(guò)7次矩陣乘法， 6次矩陣加法，和4次矩陣減法計(jì)算得出。前述的4個(gè)小矩陣可以由矩陣D到J通過(guò)6次矩陣加法和兩次矩陣減法得出. 用上述方案來(lái)解決n= 2的矩陣乘法。將某矩陣A和B相乘得結(jié)果C，如下所示：因?yàn)閚 1，所以將A、B兩矩陣分別劃分為4個(gè)小矩陣，每個(gè)矩陣為11階，僅包含一個(gè)元素。11階矩陣的乘法為小問(wèn)題，因此可以直接進(jìn)行運(yùn)算。利用計(jì)算D～J的公式，得：D= 1（68）=2E= 4（75）= 8F=（3 + 4）5 = 3 5G=（1 + 2）8 = 2 4H=（31）（5 + 6）= 2 2I=（24）（7 + 8）=3 0J=（1 + 4）（5 + 8）= 6 5根據(jù)以上結(jié)果可得：對(duì)于上面這個(gè)22的例子，使用分而治之算法需要7次乘法和1 8次加/減法運(yùn)算。而直接使用公式（2 1），則需要8次乘法和7次加/減法。要想使分而治之算法更快一些，則一次乘法所花費(fèi)的時(shí)間必須比11次加/減法的時(shí)間要長(zhǎng)。假定S t r a s s e n矩陣分割方案僅用于n≥8的矩陣乘法，而對(duì)于n8的矩陣乘法則直接利用公式（2 1）進(jìn)行計(jì)算。則n= 8時(shí)，88矩陣相乘需要7次44矩陣乘法和1 8次44矩陣加/減法。每次矩陣乘法需花費(fèi)6 4m+ 4 8a次操作，每次矩陣加法或減法需花費(fèi)1 6a次操作。因此總的操作次數(shù)為7 ( 6 4m+ 4 8a) + 1 8 ( 1 6a) = 4 4 8m+ 6 2 4a。而使用直接計(jì)算方法，則需要5 1 2m+ 4 4 8a次操作。要使S t r a s s e n方法比直接計(jì)算方法快，至少要求5 1 24 4 8次乘法的開(kāi)銷(xiāo)比6 2 44 4 8次加/減法的開(kāi)銷(xiāo)大?；蛘哒f(shuō)一次乘法的開(kāi)銷(xiāo)應(yīng)該大于近似2 . 7 5次加/減法的開(kāi)銷(xiāo)。假定n1 6的矩陣是一個(gè)“小”問(wèn)題，S t r a s s e n的分解方案僅僅用于n≥1 6的情況，對(duì)于n1 6的矩陣相乘，直接利用公式（ 2 1）。則當(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ì)算時(shí)需要4 0 9 6m+ 3 8 4 0a次操作。若一次乘法的開(kāi)銷(xiāo)與一次加/減法的開(kāi)銷(xiāo)相同，則S t r a s s e n方法需要7 8 7 2次操作及用于問(wèn)題分解的額外時(shí)間，而直接計(jì)算方法則需要7 9 3 6次操作加上程序中執(zhí)行f o r循環(huán)以及其他語(yǔ)句所花費(fèi)的時(shí)間。即使直接計(jì)算方法所需要的操作次數(shù)比St r a s s e n方法少，但由于直接計(jì)算方法需要更多的額外開(kāi)銷(xiāo)，因此它也不見(jiàn)得會(huì)比S t r a s s e n方法快。n 的值越大，Strassen 方法與直接計(jì)算方法所用的操作次數(shù)的差異就越大，因此對(duì)于足夠大的n，Strassen 方法將更快。設(shè)t (n) 表示使用Strassen 分而治之方法所需的時(shí)間。因?yàn)榇蟮木仃嚂?huì)被遞歸地分割成小矩陣直到每個(gè)矩陣的大小小于或等于k（k至少為8，也許更大，具體值由計(jì)算機(jī)的性能決定）. 用迭代方法計(jì)算，可得t(n) = (nl og27 )。因?yàn)閘 og27 ≈2 . 8 1，所以與直接計(jì)算方法的復(fù)雜性(n3 )相比，分而治之矩陣乘法算法有較大的改進(jìn)。注意事項(xiàng)分而治之方法很自然地導(dǎo)致了遞歸算法的使用。在許多例子里，這些遞歸算法在遞歸程序中得到了很好的運(yùn)用。實(shí)際上，在許多情況下，所有為了得到一個(gè)非遞
環(huán)評(píng)公示相關(guān)推薦
鄂ICP備17016276號(hào)-1