算法设计与分析第5-6讲

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

1、智能信息处理研究中心（RCIIP）第第22章章递归与分治策略递归与分治策略潘海为1智能信息处理研究中心（RCIIP）大整数的乘法请设计一个有效的算法，可以进行两个n位大整数的乘法运算P小学的方法：O(n2)效率太低分治法:X=abY=cdaX=a2n/2+bY=c2n/2+dnXY=ac2n+(ad+bc)2n/2+bd2智能信息处理研究中心（RCIIP）大整数的乘法请设计一个有效的算法，可以进行两个n位大整数的乘法运算P小学的方法：O(n2)效率太低分治法:X=复杂度分析abO)1(n1T(n)aY=c4

2、T(n/)2dO(n)n1T(n)=O(n2)没有改进X=a2n/2+bY=c2n/2+dnXY=ac2n+(ad+bc)2n/2+bd3智能信息处理研究中心（RCIIP）大整数的乘法请设计一个有效的算法，可以进行两个n位大整数的乘法运算P小学的方法：O(n2)效率太低分治法:XY=ac2n+(ad+bc)2n/2+bd为了降低时间复杂度，必须减少乘法的次数。a1.XY=ac2n+((a-c)(b-d)+ac+bd)2n/2+bd2.XY=ac2n+((a+c)(b+d)-ac-bd)2n/2+bdn4智能信息处理研

3、究中心（RCIIP）大整数的乘法请设计一个有效的算法，可以进行两个n位大整数的乘法运算P小学的方法：O(n2)效率太低复杂度分析分治法:O)1(n1T(n)XY=ac2n+(ad+bc)23Tn/2(n+)2/bdO(n)n1为了降低时间复杂度，必须减少乘法的次数。T(n)=O(nlog3)=O(n1.59)较大的改进a1.XY=ac2n+((a-c)(b-d)+ac+bd)2n/2+bd2.XY=ac2n+((a+c)(b+d)-ac-bd)2n/2+bdn细节问题：两个XY的复杂度都是O(nlog3)，

4、但考虑到a+c,b+d可能得到m+1位的结果，使问题的规模变大，故不选择第2种方案。5智能信息处理研究中心（RCIIP）大整数的乘法请设计一个有效的算法，可以进行两个n位大整数的乘法运算P小学的方法：O(n2)效率太低分治法:O(n1.59)较大的改进更快的方法??a如果将大整数分成更多段，用更复杂的方式把它们组合起来，将有可能得到更优的算法。最终的，这个思想导致了快速傅利叶变换(FastFourierTransform)的产生。该方法也可以看作是一个复杂的分治算n法。6智能信息处理研究中心（RCIIP）Stras

5、sen矩阵乘法传统方法：O(n3)PnA和B的乘积矩阵C中的元素C[i,j]定义为:C[i][j]A[i][k]B[k][j]k1若依此定义来计算A和B的乘积矩阵C，则每计a算C的一个元素C[i][j]，需要做n次乘法和n-1次加法。因此，算出矩阵C的个元素所需的计算时间为O(n3)n7智能信息处理研究中心（RCIIP）Strassen矩阵乘法传统方法：O(n3)P分治法:使用与上例类似的技术，将矩阵A，B和C中每一矩阵都分块成4个大小相等的子矩阵。由此可将方程C=AB重写为：C11C12A11A12B11

6、B12aCCAABB212221222122由此可得：CABAB1111111221CABAB12111212n22CABAB2121112221CABAB22211222228智能信息处理研究中心（RCIIP）Strassen矩阵乘法传统方法：O(n3)P分治法:使用与上例类似的技术，将矩阵A，B和C中每一矩阵都分块成4个大小相等的子矩阵。由此可将方程复杂度分析OC=AB)1(重写为：n2T(n)2C11C127AT11(nA12)2/BO11(nB12)

7、n23aCCT(n)=O(nAA)BB212221222122由此可得：CABAB1111111221CABAB12111212n22CABAB2121112221CABAB22211222229智能信息处理研究中心（RCIIP）Strassen矩阵乘法传统方法：O(n3)P分治法:为了降低时间复杂度，必须减少乘法的次数。C11C12A11A12B11B12CCAABB212221222122aMA(BB)1111222M(AA)BC

8、MMMM2111222115426M(AA)B3212211CMM1212MA(BB)4222111nM(AA)(BB)C21M3M4511221122M(AA)(BB)612222122CMMMM225137M(A