strassen算法的时间复杂度.doc

Strassen 算法的时间复杂度（原创）参考书：Foundations Of Algorithms4th Edition直插重点：lg 是以2为底的log函数 至于为什么，我也不晓得，大概是这本书作者的坏习惯首先来看Strassen矩阵的乘法规则：假设我们想求矩阵C，C是2*2矩阵 A和B的乘积，给出以下规则Strassen（人名） 给出7个中间M矩阵：M1=A11(B12-B22)M2=(A11+A12)B22M3=(A21+A22)B11M4=A22(B21-B11)M5=(A11+A22)(B11+B22)M6=(A12-A22)(B21+B22)M7=(A11-A21)(B11+B12)做了这7次乘法后，再做若干次加、减法就可以得到:C11=M5+M4-M2+M6C12=M1+M2C21=M3+M4C22=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 n1 n is a number power of 2T (1)=1;令： tn=T(n)最初的几个值可以记成：t2=7t2/2=7t4=7t4/2=72t8=7t8/2=73这几个式子，表现出了：tn=7lgn我们只需证明t2n=7lg2n就能说这个式子是成立的，t2n=7t2n2=7tn=7*7lgn=71+lgn=7lg2+lgn=7lg2nOk证明完毕；那么由log函数的性质可得：7lgn=nlg7那么用科学计算机算下 lg7约等于2.81那么可以得出对于元乘法的时间复杂度： T(n)n2.812，那么在每一步加上元加法,减法就是我们要求的最终时间复杂度了。再回到递归上面：从初始的矩阵中分过一次的得到A，B，那么每次的加法加法运算是18次，在原来的基础（ T（n）=7T(n/2)）上加上加上 也就是 T（n）=7Tn2+18n22 for :n1 , nis a power of 2 T(1)=0 最后可解得 T（n）=6nlg7-6n26n2.81-6n2有细心的同学也许发现，这个式子是在上面元乘法的式子上加上18n22得来的，为什么最后得出的值可能还没元乘法的时间复杂大？why。 因为下面有条件 T(1)=0 ，这个条件什么意思？就是让元乘法的时间复杂度为0 那么根据这些我们可以得出 Strassen算法总得时间复杂度 = 元乘法