![[C11 C12 ] [A11 A12 ] [B11 B12 ]
= ×
C21 C22 A21 A22 B21 B22](http://www.cse.ohio-state.edu/~gurari/course/cse693s04/cse693s04135x.gif)
普通方法
C11 =A11*B11+A12*B21
C12=。。
C21=。。。
C22=。。。
此遞歸公式為T(n)=8T(n/2)+O(n^2) 時間復(fù)雜度為O(n^3)
Strassen方法的遞推公式為：
T(n) = O(nlog 7) = O(n2.81).
時間復(fù)雜度就馬上降下來了。。但是不要過于樂觀。
從實用的觀點看，Strassen算法通常不是矩陣乘法所選擇的方法：
1 在Strassen算法的運(yùn)行時間中，隱含的常數(shù)因子比簡單的O(n^3)方法常數(shù)因子大
2 當(dāng)矩陣是稀疏的時候，為稀疏矩陣設(shè)計的算法更快
3 Strassen算法不像簡單方法那樣子具有數(shù)值穩(wěn)定性
4 在遞歸層次中生成的子矩陣要消耗空間。
所以矩陣乘法一般意義上還是選擇的是樸素的方法，只有當(dāng)矩陣變稠密，而且矩陣的階數(shù)>20左右，才會考慮使用Strassen算法。