• / 18
  • 下载费用:10 金币  

算法设计与分析第3讲 分治法.ppt

关 键 词:
算法设计与分析第3讲 分治法.ppt
资源描述:
1,3.1 分治法的基本思想,分治法的基本思想 分治法的基本思想是将一个规模为n的问题分解为k个规模较小的子问题,这些子问题互相独立且与原问题相同。 对这k个子问题分别求解。如果子问题的规模仍然不够小,则再划分为k个子问题,如此递归的进行下去,直到问题规模足够小,很容易求出其解为止。 将求出的小规模的问题的解合并为一个更大规模的问题的解,自底向上逐步求出原来问题的解。 分治法的设计思想是,将一个难以直接解决的大问题,分割成一些规模较小的相同问题,以便各个击破,分而治之。,凡治众如治寡,分数是也。 ——孙子兵法,2,3.1分治法的基本思想,分治法的基本步骤 divide-and-conquer(P) {if ( | P | = n0) adhoc(P); //解决小规模的问题divide P into smaller subinstances P1,P2,.,Pa;//分解问题for (i=1,i=a,i++)yi=divide-and-conquer(Pi); //递归的解各子问题return merge(y1,.,ya); //将各子问题的解合并为原问题的解 } 人们从大量实践中发现,在用分治法设计算法时,最好使子问题的规模大致相同。即将一个问题分成大小相等的k个子问题的处理方法是行之有效的。这种使子问题规模大致相等的做法是出自一种平衡(balancing)子问题的思想,它几乎总是比子问题规模不等的做法要好。,3,3.1分治法的基本步骤,分治法的复杂性分析 一个分治法将规模为n的问题分成a个规模为n/b的子问题去解。设分解阀值n0=1,且adhoc解规模为1的问题耗费1个单位时间。再设将原问题分解为k个子问题以及用merge将k个子问题的解合并为原问题的解需用f(n)个单位时间。用T(n)表示该分治法解规模为|P|=n的问题所需的计算时间,则有,4,3.2 合并排序,1分为两个半表 2每个表递归排序 3合并 (f(n)=θ(n))T(n)=2T(n/2)+ θ(n) 主方法case 2 , T(n)= θ(n.lgn),5,3.3 二分搜索技术,给定已按升序排好序的n个元素a[1:n],现要在这n个元素中找出一特定元素x。,6,算法及其复杂性,据此容易设计出二分搜索算法: public int binarySearch(int [] a, int x, left, right) { // 在 a[start] a[middle]) return binarySearch[a,x,middle,rught]; Else return binarySearch[a,x,left, midle]; } 算法复杂度分析:T(n)= T(n/2) + θ(1), case 2: θ(logn)。,7,3.4 大整数的乘法,设计一个有效的算法,可以进行两个n位大整数的乘法运算 小学的方法: θ(n2) 效率太低 分治法: X=a2n/2+b Y=c2n/2+d XY=ac2n+(ad+bc)2n/2+bd 复杂度分析Case 1: T(n)= θ(n2) 没有改进,8,算法改进,为了降低时间复杂度,必须减少乘法的次数。为此,我们把XY写成另外的形式: XY = ac 2n + ((a-b)(d-c)+ac+bd) 2n/2 + bd 或 XY = ac 2n + ((a+b)(c+d)-ac-bd) 2n/2 + bd 复杂性: 这两个算式看起来更复杂一些,但它们仅需要3次n/2位乘法[ac、bd和(a±c)(b±d)],于是T(n)= θ(nlog3) = θ(n1.59) 较大的改进 细节问题:两个XY的复杂度都是O(nlog3),但考虑到a+b,c+d可能得到m+1位的结果,使问题的规模变大,故不选择第2种方案。,9,3.5 Strassen矩阵乘法,n×n矩阵A和B的乘积矩阵C中的元素C[i,j]定义为:若依此定义来计算A和B的乘积矩阵C,则每计算C的一个元素C[i][j],需要做n次乘法和n-1次加法。因此,算出矩阵C的n*n 个元素所需的计算时间为θ(n3),10,简单分治法求矩阵乘,首先假定n是2的幂。使用与上例类似的技术,将矩阵A,B和C中每一矩阵都分块成4个大小相等的子矩阵。由此可将方程C=AB重写为:由此可得:复杂度分析Case 1: T(n)= θ(n3) 没有改进,11,改进算法,为了降低时间复杂度,必须减少乘法的次数。而其关键在于计算2个2阶方阵的乘积时所用乘法次数能否少于8次。为此,Strassen提出了一种只用7次乘法运算计算2阶方阵乘积的方法(但增加了加/减法次数): M1=A11(B12-B22) M2=(A11+A12)B22 M3=(A21+A22)B11 M4=A22(B21-B1
展开阅读全文
  微传网所有资源均是用户自行上传分享,仅供网友学习交流,未经上传用户书面授权,请勿作他用。
0条评论

还可以输入200字符

暂无评论,赶快抢占沙发吧。

关于本文
本文标题:算法设计与分析第3讲 分治法.ppt
链接地址:https://www.weizhuannet.com/p-10071431.html
微传网是一个办公文档、学习资料下载的在线文档分享平台!

微传网博客

网站资源均来自网络,如有侵权,请联系客服删除!

 网站客服QQ:80879498  会员QQ群:727456886

copyright@ 2018-2028 微传网络工作室版权所有

     经营许可证编号:冀ICP备18006529号-1 ,公安局备案号:13028102000124

收起
展开