strassen算法的时间复杂度.doc_第1页
strassen算法的时间复杂度.doc_第2页
strassen算法的时间复杂度.doc_第3页
strassen算法的时间复杂度.doc_第4页
全文预览已结束

下载本文档

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

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算法总得时间复杂度 = 元乘法

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

评论

0/150

提交评论