原理
- 矩阵相加需花费Θ(n2)时间,而递归分为8个子问题矩阵相乘花费Θ(n3)时间.strassen算法减少每层递归子问题的个数,以矩阵相加替换,从而达到减少时间复杂度
比如(a)(c+d)和ac+ad作乘法的次数不一样,可以从这个简单的例子直观的感受原理
实现的理解
如果想要直观的理解,那么好的方式是用图形代替代数公式,下面的内容就是基于这个想法
1.代数公式和图形的联系
对于ab,我们可以把它看作是一个线段,a和b是它的两个端点
那么ab+a*c,即a(b+c)就是由两个线段组成的,它们共同的点是a
进一步,(a+b)(c+d)可以看作是一个四边形,四点是a,b,c,d,四条边就是它们的项.如下图:
联系图
当然a,b,c,d的正负都行
2.strassen算法的直观效果
根据以上的想法,我们可以把strassen算法过程画成以下的效果
直观效果.jpg
其中实线代表我们想要得到的矩阵乘法的项,如下
C11=A11⋅B11+A12⋅B21
C12=A11⋅B12+A12⋅B21
C21=A21⋅B11+A22⋅B21
C22=A21⋅B12+A22⋅B22
-
两项不在个一面时
以C11=A11⋅B11+A12⋅B21为例,在图中以"+"标注,想要得到这两个线,要用 四边形A22B21A12B22 和 四边形A11B11A22B22 相加并减去重复的边 A22B22,A11B22,B22A12,B11A22,A22B21, 图中以和边相交的"="标注.如下图
IMG_20190106_124854.jpg
A22B22是两个四边形的重复线段,可以使它在两个四边形的正负不同相抵
A11B22和B22A12是由两条线段组成,可以看作是B22(A11+A12)
同样B11A22,A22B21可以看作是A22(B11+B21)
所以最终是由(A22+A12)(B21+B22)+(A11+A22)(B11+B22)+B22(A11+A12)+A22(B11+B21)通过调整正负号可以得到A11⋅B11+A12⋅B21
- 两项在一个面时
例如C12=A11⋅B12+A12⋅B21,可以通过A11(B12+B22)+B22(A11+A12)得到
总结
通过类比,有时能够更方便的理解和记忆
