学步园

 本篇文章主要介绍的是递归式的求解方法，strassen算法理论价值高于实际价值。

 求解递归式的方法有三种：

1. 代入法。猜测解的形式，然后用数学归纳法证明；
2. 递归树法，这个方法简单易用；
3. 主方法：对于形如：T(n)=aT(n/b)+f(n)  （a>=1 ,b>1)

朴素矩阵乘法伪码：

SQUARE-MATRIX-MULTIPLY(A,B)
  n=A.rows
  let C be a new matrix
  for i=1 to n
     for j=1 to n
	     cij=0
		 for k=1 to n
		    cij=cij+aik+bkj

  return C

其运行时间为theta(n^3)

Strassen算法的运行时间是theta(n^2.81)

对于C=A*B：

这样分解可降低乘法运算的规模；

即使这样，我们需要做对于n/2*n/2规模的矩阵乘法做8次，矩阵加法做4*n^2/4=n^2次，写出递归式如下：

T(n) =   theta(1)          n=1

       =8T(n/2)+theta(n^2)   n>1

根据主方法：a=8,b=2,f(n)=theta(n^2),我们知道这属于第一种情况，此时得T(n)=theta(n^3)

再加上多出来的常数因子，这种方法效率低于朴素矩阵乘法；

而Strassen算法的运行时间却是T(n)=7T(n/2)+theta(n^2)，这样一来时间复杂度成为theta(n^2,81)，具体做法如下：

1.先定义十个矩阵S1...10：

这共进行了10次n/2*n/2的矩阵加减法，花费theta(n^2)

2.再定义7个矩阵P1...7，进行7次n/2*n/2乘法：

3.最后得：

   C11=P5+P4-P2+P6

   C12=P1+P2

   C21=P3+P4

   C22=P5+P1-P3-P7

 总8次n/2*n/2矩阵加减法，花费theta(n^2)

strassen算法的具体代码后面同矩阵运算，稀疏矩阵乘法等一块实现；

从实用角度，Strassen算法通常不是一个好的选择：

1.隐藏在运行时间theta(N^2.81)后面的常数因子极大，当n>2000时，才能保证效率高于朴素矩阵乘法；

2.对于稀疏矩阵，专用算法更快；

3.Strassen算法数值稳定性不高；

4.消耗空间大；