strassen算法的时间复杂度.doc

Strassen 算法的时间复杂度（原创）
参考书：《Foundations Of Algorithms》4th Edition
直插重点：lg 是以2为底的log函数 至于为什么，我也不晓得，大概是这本书作者的坏习惯
首先来看Strassen矩阵的乘法规则：
假设我们想求矩阵C，C是2*2矩阵 A和B的乘积，给出以下规则

Strassen（人名） 给出7个中间M矩阵：
M1=A11(B12-B22)
M2=(A11+A12)B22
M3=(A21+A22)B11
M4=A22(B21-B11)
M5=(A11+A22)(B11+B22)
M6=(A12-A22)(B21+B22)
M7=(A11-A21)(B11+B12)
做了这7次乘法后，再做若干次加、减法就可以得到:　
C11=M5+M4-M2+M6
C12=M1+M2
C21=M3+M4
C22=M5+M1-M3-M7
那么：
;
至于为什么，请去网上找，不找也没关系，这只是一个公式，我只是写一些网上很难找到的东西，或者是要在网站上花钱买的东西：
那么我们看：
每一步有7歩元乘法（elementary multiplication）元乘法是一种宏观的乘法，并不是真实的元素之间的乘法，至于这个元是什么东西，它是一个矩阵，是一个单元。本文中是指特定的矩阵之间的乘法，元加法，减肥同理。
和18歩元加法、减法（elementary addition、subtraction）
1，首先先以元乘法做为一个基础运算，求出关于时间的复杂度：
需要的数据：n 矩阵的列数和行数（相等的）
递归学的好的可以跳过下面一段：
假设n为2的乘方数（n a power of 2，中文不知道怎么翻译 囧），那么我们在逐步分割时，直到把C分成1*1的矩阵前，我们可以做lgn次分割，（怎么分？请拿出笔，按我说的画下，不画的估计看不懂，可以点击本页上面那个X退出了，把A和B先平均分成4快，你会神奇的看到，A会变成一个2*2的矩阵，我们可以叫它矩阵的矩阵，同理，B也这样搞，现在得出了两个2*2的矩阵，就可以用上面那个公式了，用Strassen矩阵的乘法规则得出下一次递归用的C，下次递归可以分割这个C成下次的AB，这样递归下去）
只考虑乘法那么算法的时间复杂度：T（n）=7T(n/2); 每一步有7次乘法运算，那么第一次的时间复杂度是第二次的7倍，依次类推，知道矩阵被分成一个1*1的矩阵。 冥想吧，冥想是搞算法的一个途径。
那么我们可以得出下面关于元乘法运算的时间
T（n）=7T(n/2); for n>1 n is a number power of 2
T (1)=1;
令： tn=T(n)
最初的几个值可以记成：
t2=7t2/2=7
t4=7t4/2=72
t8=7t8/2=73
这几个式子，表现出了：
tn=7lgn
我们只需证明
t2n=7lg2n
就能说这个式子是成立的，
t2n=7t2n2=7tn=7*7lgn=71+lgn=7lg2+lgn=7lg2n
Ok证明完毕；
那么由log函数的性质可得：
7lgn=nlg7
那么用科学计算机算下 lg7约等于2.81
那么可以得出对于元乘法的时间复杂度： T(n)≈n2.81
2，那么在每一步加上元加法,减法就是我们要求的最终时间复杂度了。
再回到递归上面：
从初始的矩阵中分过一次的得到A，B，那么每次的加法加法运算是18次，在原来的基础（ T（n）=7T(n/2)）上加上加上 也就是
T（n）=7Tn2+18n22 for :n>1 , nis a power of 2
T(1)=0
最后可解得 T（n）=6nlg7-6n2≈6n2.81-6n2
有细心的同学也许发现，这个式子是在上面元乘法的式子上加上18n22得来的，为什么最后得出的值可能还没元乘法的时间复杂大？why。。 因为下面有条件 T(1)=0 ，这个条件什么意思？就是让元乘法的时间复杂度为0
那么根据这些我们可以得出 Strassen算法总得时间复杂度 = 元乘法的时间复杂度+元加,减法的时间复杂度=7n2.81-6n2
最终解释权归： yuanxi_china@ 所有
student of （ hhu & knu ）