![[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) 时间复杂度为O(n^3)
Strassen方法的递推公式为：
T(n) = O(nlog 7) = O(n2.81).
时间复杂度就马上降下来了。。但是不要过于乐观。
从实用的观点看，Strassen算法通常不是矩阵乘法所选择的方法：
1 在Strassen算法的运行时间中，隐含的常数因子比简单的O(n^3)方法常数因子大
2 当矩阵是稀疏的时候，为稀疏矩阵设计的算法更快
3 Strassen算法不像简单方法那样子具有数值稳定性
4 在递归层次中生成的子矩阵要消耗空间。
所以矩阵乘法一般意义上还是选择的是朴素的方法，只有当矩阵变稠密，而且矩阵的阶数>20左右，才会考虑使用Strassen算法。