算法分析与设计2003秋.课件.第02讲

《算法分析与设计2003秋.课件.第02讲》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、Lecture02Dynamicprogramming第一次课后问题汇总•考试成绩：免考由平时成绩和综合练习质量计算，考试者以平时成绩％50＋50％考试成绩。•答疑问题：网上答疑1问题（续）•认为容易的讲的慢，要加快速度。•讲解思想，少细节•整个学科的背景线条，并重点强调基本概念；•对文献的检索方式作简要介绍。•算法实现时可能遇到的问题给我们指点一下问题（续）•算法设计的经验，思路和方法•补充一下这些基础课的内容•重点难点•希望老师能在授课过程中穿插讲授一些跟实际工程实际结合得更紧密的内容•前沿问题进行一些概要•课堂上适

2、当地讲一些基础知识2问题（续）•课程不但立足于让同学们知道已有的算法，还有尽可能的引导同学设计出新的算法•轻松幽默问题（续）•对整数乘法有个别同学不大明白•关于SCI、EI说明3关于剽窃与抄作业•讨论：什么是抄作业？什么是引用？什么叫你自己的研究成果？什么是别人的成果？ReviewofDivideandConquer•分：•治：•合：•递推公式。T(n)=aT(n/b)+f(n)4Strassen矩阵乘法•矩阵相乘的分治算法（Strassen）•其它的算法矩阵乘法是线性代数中最常见的问题之一，它在数值计算中有广泛的应用。

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

4、B和C中每一矩阵都分块成4个大小相等的子矩阵【假设n是2幂】，每个子矩阵都是（n/2）×（n/2）的方阵。由此可将方程C＝AB重写为：C11C12A11A12B11B12=CCAABB212221222122利用矩阵块乘可得：C=AB+AB1111111221C=AB+AB1211121222C=AB+AB2121112221C=AB+AB2221122222如果n＝2，则2个2阶方阵的乘积可以直接计算出来，共需8次乘法和4次加法。当子矩阵的阶大于2时，为求2个子矩阵的积，可以继续将子

5、矩阵分块，直到子矩阵的阶降为2。由此产生分治降阶的递归算法。依此算法，计算2个n阶方阵的乘积转化为计算8个n/2阶方阵的乘积和4个n/2阶方阵的加法。2个（n/2）×（n/2）矩阵的加法显然可以在O（n2）时间内完成。因此，上述分治法的计算时间耗费T（n）应满足：O(1)n=2T(n)=28T(n/2)+O(n)n>26这个递归方程的解仍然是T(n)=O(n3)。因此，该方法并不比用原始定义直接计算更有效。究其原因，乃是由于该方法并没有减少矩阵的乘法次数。而矩阵乘法耗费的时间要比矩阵加（减）法耗费的时间多得多。要想

6、改进矩阵乘法的计算时间复杂性，必须减少乘法运算。按照上述分治法的思想可以看出，要想减少乘法运算次数，关键在于计算2个2阶方阵的乘积时，能否用少于8次乘法运算。Strassen提出了一种新的算法来计算2个2阶方阵的乘积。只用7次乘法运算Strassen发现通过7次乘法运算：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得到C

7、等值11C＝M＋M－M＋M115426C＝M＋M1212C＝M＋M2134C＝M＋M－M－M225137效果Strassen矩阵乘法中，用了7次对于n/2阶矩阵乘的递归调用和18次n/2阶矩阵的加减运算。由此可知，该算法所需的计算时间T(n)满足如下的递归方程：O(1)n=2T(n)=27T(n/2)+O(n)n>2解此递归方程得T(n)=O(nlog7)≈O(n2.81)。由此可见，Strassen矩阵乘法的计算时间复杂性比普通矩阵乘法有较大改进。8Strassen是如何发现的？•谁知道？•一种可能的方法：分析法

8、–4个式子–8种基本元素AijBij–有可能用少于8次乘法完成–如何利用7次乘法计算【具体参见P736】？最后讨论•Hopcroft和Kerr在1971年已经证明，计算2个2×2矩阵的乘积，7次乘法是必要的。•Strassen之后又有许多算法改进了矩阵乘法的计算时间复杂性。目前最好的计算时间上界是O(n2.376)。