O(1) 的小樂(lè)

普通方法

C11 =A11*B11+A12*B21

C12=。。

C21=。。。

C22=。。。

此遞歸公式為T(n)=8T(n/2)+O(n^2)  時(shí)間復(fù)雜度為O(n^3)

Strassen方法的遞推公式為：

T(n) = O(n^{log 7}) = O(n^2.81).

時(shí)間復(fù)雜度就馬上降下來(lái)了。。但是不要過(guò)于樂(lè)觀。

從實(shí)用的觀點(diǎn)看，Strassen算法通常不是矩陣乘法所選擇的方法：

1 在Strassen算法的運(yùn)行時(shí)間中，隱含的常數(shù)因子比簡(jiǎn)單的O(n^3)方法常數(shù)因子大

2 當(dāng)矩陣是稀疏的時(shí)候，為稀疏矩陣設(shè)計(jì)的算法更快

3 Strassen算法不像簡(jiǎn)單方法那樣子具有數(shù)值穩(wěn)定性

4 在遞歸層次中生成的子矩陣要消耗空間。

所以矩陣乘法一般意義上還是選擇的是樸素的方法，只有當(dāng)矩陣變稠密，而且矩陣的階數(shù)>20左右，才會(huì)考慮使用Strassen算法。