算法分析与设计2005春02 清华大学：算法分析与设计

《算法分析与设计2005春02 清华大学：算法分析与设计》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、ReviewofDivideandConquern分：如何分：要考虑合Lecture02动态规划n治：如何治：递归＋临界条件下使用其它方法n合：艺术！！！n递推公式。T(n)=aT(n/b)+f(n)nMaster定理：控制定理清华大学宋斌恒清华大学宋斌恒1清华大学宋斌恒2矩阵乘法是线性代数中最常见的问题之一，它在数值计Strassen矩阵乘法算中有广泛的应用。设A和B是2个n×n矩阵，它们的乘积AB同样是一个n×n矩阵。A和B的乘积矩阵C中元素C[i][j]定义为：nn矩阵相乘的分治算法（St

2、rassen）C[i][j]=åA[i][k]B[k][j]k=1n其它的算法若依此定义来计算A和B的乘积矩阵C，则每计算C的一个元素C[i][j]，需要做n次乘法运算和n－1次加法运算。因此，算出矩阵C中的n2个元素所需的计算时间为O（n3）。20世纪60年代末期，Strassen采用了类似于在大整数乘法中用过的分治技术，将计算2个n阶矩阵乘积所需的计算时间改进到O（nlog7）=O（n2.81）,其基本思想还是使用分治法。清华大学宋斌恒3清华大学宋斌恒4将矩阵A，B和C中每一矩阵都分块成4个

3、大小相等的子如果n＝2，则2个2阶方阵的乘积可以直接计算出来，矩阵【假设n是2幂】，每个子矩阵都是（n/2）×（n/2）共需8次乘法和4次加法。当子矩阵的阶大于2时，为求2个的方阵。由此可将方程子矩阵的积，可以继续将子矩阵分块，直到子矩阵的阶降C＝AB重写为：为2。由此产生分治降阶的递归算法。依此算法，计算2个n阶方阵的乘积转化为计算8个n/2阶方阵的乘积和4个n/2éC11C12ùéA11A12ùéB11B12ù阶方阵的加法。2个（n/2）×（n/2）矩阵的加法显然可êú=êúêú以在O（n2

4、）时间内完成。因此，上述分治法的计算时间ëC21C22ûëA21A22ûëB21B22û耗费T（n）应满足：利用矩阵块乘可得：C=AB+AB1111111221C12=A11B12+A12B22ìO(1)n=2C=AB+ABT(n)=í22121112221î8T(n/2)+O(n)n>2C22=A21B12+A22B22清华大学宋斌恒5清华大学宋斌恒61这个递归方程的解仍然是T(n)=O(n3)。因此，该方法并不比用原始定义直接计算更有效。究其原只用7次乘法运算因，乃是由于该方法并没有减少矩阵

5、的乘法次数。而矩阵乘法耗费的时间要比矩阵加（减）法耗费的Strassen发现通过7次乘法运算：时间多得多。要想改进矩阵乘法的计算时间复杂M1=A11(B12－B22)性，必须减少乘法运算。M2=(A11+A12)B22按照上述分治法的思想可以看出，要想减少乘M3=(A21+A22)B11法运算次数，关键在于计算2个2阶方阵的乘积时，M4=A22(B21－B11)能否用少于8次乘法运算。Strassen提出了一种新的M5=(A11+A22)(B11+B22)算法来计算2个2阶方阵的乘积。M6=(A

6、12－A22)(B21+B22)M7=(A11－A21)(B11+B12)清华大学宋斌恒7清华大学宋斌恒8得到C11等值效果C11＝M5＋M4－M2＋M6Strassen矩阵乘法中，用了7次对于n/2阶矩阵乘的递归调用和18次n/2阶矩阵的加减运算。由此可知，该算法所C12＝M1＋M2需的计算时间T(n)满足如下的递归方程：C21＝M3＋M4T(n)=ìO(1)n=2í2C22＝M5＋M1－M3－M7î7T(n/2)+O(n)n>2解此递归方程得T(n)=O(nlog7)≈O(n2.81)。由此

7、可见，Strassen矩阵乘法的计算时间复杂性比普通矩阵乘法有较大改进。清华大学宋斌恒9清华大学宋斌恒10Strassen是如何发现的？讨论n谁知道？n一种可能的方法：分析法nHopcroft和Kerr在1971年已经证明，计算2个2×2矩阵的乘积，7次乘法是必要的。n4个式子nStrassen之后又有许多算法改进了矩阵乘法的计算时间n8种基本元素AB2.376ijij复杂性。目前最好的计算时间上界是O(n)。n有可能用少于8次乘法完成n实际使用很少，有4条理由n如何利用7次乘法计算【具体参见P

8、736】？1.阶数低系数大【CrossPoint,不同情况下n=8[Hignam],12[Huss-Lederman],20[实际]，用试验方法】2.稀疏矩阵有更好方法3.数值稳定性不够4.占用空间大清华大学宋斌恒11清华大学宋斌恒122Assemblylinescheduling有关算法的实现和实用化StationStationStationStation1,11,21,31,naaaanStrassen算法实现注意事项：1,11,21,31,nex1n如何一般化？1tt1,21,1n递归到什