国产成人精品三级麻豆,色综合天天综合高清网,亚洲精品夜夜夜,国产成人综合在线女婷五月99播放,色婷婷色综合激情国产日韩

二維數(shù)組無(wú)論在數(shù)值計(jì)算領(lǐng)域還是在非數(shù)值計(jì)算領(lǐng)域都是一種相當(dāng)基本、重要且抽象的數(shù)據(jù)結(jié)構(gòu)。二維數(shù)組在數(shù)學(xué)中的表現(xiàn)形式是矩陣，因此研究 矩陣的基本運(yùn)算本質(zhì)上就是在研究二維數(shù)組的運(yùn)算。顯然，盡可能地提高矩陣運(yùn)算速率對(duì)于編程而言是十分重要的工作。

矩陣加法和矩陣乘法是矩陣中基本的矩陣運(yùn)算。設(shè)A、B是兩個(gè)n×n的矩陣。矩陣的加法表示兩個(gè)矩陣對(duì)應(yīng)位置元素之和，因此它們的和仍然是一 個(gè)n×n的矩陣，記為C=A+B。顯然，矩陣加法的時(shí)間復(fù)雜度為O(n2)。

如果設(shè)矩陣A與B的乘積為矩陣C，即C=A×B，顯然矩陣C也是一個(gè)n×n的矩陣。則矩陣C的第i行第j列的元素C(I,j)等于矩陣A的第i行和矩陣B的第j 列對(duì)應(yīng)元素乘積的和�？杀硎緸椋�

按這個(gè)公式計(jì)算C(i,j)需要n次乘法與n-1次加法，而矩陣C中有n×n個(gè)元素，因此，由矩陣乘法定義而直接產(chǎn)生的矩陣相乘算法時(shí)間復(fù)雜度為O(n3) 。

人們長(zhǎng)期對(duì)矩陣的乘法計(jì)算的改進(jìn)工作做著不懈的努力，做出不少嘗試，也試圖設(shè)計(jì)或改進(jìn)這個(gè)算法，但無(wú)論怎樣改進(jìn)都囿于O(n3)數(shù)量級(jí)的時(shí)間 復(fù)雜度，沒(méi)有顯著地提速。

1969年，斯特拉森（V.Strassen）利用分治策略并加上數(shù)學(xué)處理設(shè)計(jì)出了一種時(shí)間復(fù)雜度是O(n2.81)（準(zhǔn)確地說(shuō)是O(nlog7)）的矩陣相乘算法，宣 稱在時(shí)間復(fù)雜度數(shù)量級(jí)上有所突破。此結(jié)果一發(fā)布，立即震動(dòng)了整個(gè)數(shù)學(xué)界。

為簡(jiǎn)單描述這一算法，我們假定矩陣C的階數(shù)是2的冪，即存在一個(gè)非負(fù)正數(shù)k使得n=2k。若n不是2的冪，則可通過(guò)適當(dāng)添加全零行和全零列來(lái)構(gòu)造 成2的冪的方陣。

按照分治策略，首先將矩陣A與B分解成4個(gè)(n/2)×(n/2)矩陣，即：

對(duì)A和B每個(gè)(n/2)×(n/2)矩陣進(jìn)行矩陣乘法運(yùn)算即可得到C。其中：

C11=A11B11+A12B21

C12=A11B12+A12B22

C21=A21B11+A22B21

C22=A21B12+A22B22

使用通常的矩陣乘法與加法計(jì)算分別得到C11、C12、C21、C22四個(gè)子矩陣，那么顯然可以得出分塊子矩陣拼接后的矩陣就是矩陣C。如果分塊子矩陣階 數(shù)仍然大于2，則可繼續(xù)用此方式將分塊子矩陣劃分為更小的4塊，直至每個(gè)子矩陣都只有1個(gè)元素以至于可以直接計(jì)算其乘積為止。對(duì)于使用分塊子矩 陣計(jì)算C的方法，顯然需要8次乘法與4次加法，由于每?jī)蓚�(gè)n/2級(jí)方陣的計(jì)算都可以在某個(gè)可預(yù)見(jiàn)的時(shí)間cn2（c是常數(shù)）內(nèi)完成，則通過(guò)分治法我們可 以得到T(n)的遞歸表示方法：

其中b和d是兩個(gè)常數(shù)。求解這個(gè)遞歸關(guān)系式：

可以看出，這種方式與通常的矩陣乘法計(jì)算時(shí)間復(fù)雜度一樣。究其原因，這種方法仍然是使用8次乘法與4次加法。若無(wú)法有效降低乘法的次數(shù)，則仍 然無(wú)法有效降低時(shí)間復(fù)雜度。

斯特拉森在分治法的基礎(chǔ)上，設(shè)計(jì)出了一種7次乘法的處理方式。其處理方式是：先使用7個(gè)乘法10個(gè)加法計(jì)算7個(gè)等式：

P=(A11+A22)(B11+B22)

Q=(A21+A22)B11

R=A11(B12-B22)

S=A22(B21-B11)

T=(A11+A12)B22

U=(A21-A11)(B11+B12)

V=(A12-A22)(B21+B22)

然后使用8個(gè)加法將這7個(gè)等式構(gòu)造成C：

C11=P+S-T+V

C12=R+T

C21=Q+S

C22=P+R-Q+U

以上共使用7次乘法與18次加法。

則由T(n)所得的遞歸公式是：

推導(dǎo)時(shí)間復(fù)雜度的過(guò)程類似上文，這里不再贅述。終可得時(shí)間復(fù)雜度為O(nlog7)≈O(n2.81)。

在斯特拉森之后，許多人也試圖繼續(xù)改進(jìn)該算法。其中，J.E.Hopcroft和L.R.Kerr已經(jīng)證明，兩個(gè)2的冪階矩陣相乘必須要使用7次乘法無(wú)法再簡(jiǎn)化。 若想再進(jìn)一步簡(jiǎn)化則必須考慮劃分為3的冪或4的冪以及更高級(jí)的冪階才有意義。因此分治策略必須改變，即必須采取其他分治策略的設(shè)計(jì)思路才行。

后需要說(shuō)明的是，斯特拉森矩陣乘法目前只有理論意義。事實(shí)證明當(dāng)矩陣階數(shù)足夠大（n在128階以上）時(shí)，它和普通的矩陣乘法的執(zhí)行時(shí)間仍無(wú)顯 著差別。即使如此，斯特拉森矩陣乘法給我們提供了一個(gè)有益的啟示：即使從簡(jiǎn)單的定義出發(fā)來(lái)設(shè)計(jì)的算法也可能不是好的，仍然可以去優(yōu)化。

參考文獻(xiàn)：

[1]《線性代數(shù)與多項(xiàng)式的快速算法》

[2]《計(jì)算機(jī)算法基礎(chǔ)（第三版）》