• / 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-B11) M5=(A11+A22)(B11+B22) M6=(A12-A22)(B21+B22) M7=(A11-A21)(B11+B12) 做了这7次乘法后,在做若干次加/减法就可以得到: C11=M5+M4-M2+M6 C12=M1+M2 C21=M3+M4 C22=M5+M1-M3-M7 复杂度分析T(n)= θ(nlog7) = θ(n2.81) 较大的改进,12,更快的方法,Hopcroft和Kerr已经证明(1971),计算2个2×2矩阵的乘积,7次乘法是必要的。因此,要想进一步改进矩阵乘法的时间复杂性,就不能再基于计算2×2矩阵的7次乘法这样的方法了。或许应当研究3×3或5×5矩阵的更好算法。 在Strassen之后又有许多算法改进了矩阵乘法的计算时间复杂性。 目前最好的计算时间上界是 O(n2.376) 是否能找到θ(n2)的算法?目前为止还没有结果。,13,3.6 Fibonacci数列,例2 Fibonacci数列 无穷数列1,1,2,3,5,8,13,21,34,55,…,被称为Fibonacci数列。它可以递归地定义为: 第n个Fibonacci数可递归地计算如下: public static int fibonacci(int n){if (n = 1) return 1;return fibonacci(n-1)+fibonacci(n-2);} 用递归树分析,算法的复杂度是指数ψn ,,小兔子问题,14,Fibonacci数列,2 自底向上,T(n)= θ(n), 3 Gn= (Fn-1 Fn * (1 1 Fn Fn-1) 1 0Gn=XnT(n)=T(n/2)+ θ(1)T(n)=θ(lgn),15,3.7 棋盘覆盖,在一个2k×2k个方格组成的棋盘中,恰有一个方格与其他方格不同,称该方格为一特殊方格,且称该棋盘为一特殊棋盘。在棋盘覆盖问题中,要用图示的4种不同形态的L型骨牌覆盖给定的特殊棋盘上除特殊方格以外的所有方格,且任何2个L型骨牌不得重叠覆盖。 易知,覆盖任意一个2k×2k的特殊棋盘,用到的骨牌数恰好为(4K-1)/3。,16,分治策略求解,当k0时,将2k×2k棋盘分割为4个2k-1×2k-1 子棋盘(a)所示。特殊方格必位于4个较小子棋盘之一中,其余3个子棋盘中无特殊方格。为了将这3个无特殊方格的子棋盘转化为特殊棋盘,可以用一个L型骨牌覆盖这3个较小棋盘的会合处,如 (b)所示,从而将原问题转化为4个较小规模的棋盘覆盖问题。递归地使用这种分割,直至棋盘简化为棋盘1×1。,17,算法描述,void CB(int tr,tc,dr,dc,size) { if (size == 1) return; int t = tile++; // L型骨牌号 s = size/2; // 分割棋盘 // 覆盖左上角子棋盘 if (dr = tc + s) // 特殊方格在此棋盘中 CB(tr, tc+s, dr, dc, s); else {// 此棋盘中无特殊方格 // 用 t 号L型骨牌覆盖左下角 board[tr + s - 1][tc + s] = t; // 覆盖其余方格 CB(tr,tc+s,tr+s-1,tc+s, s);},// 覆盖左下角子棋盘 if (dr = tr + s } },,18,复杂度分析,说明: 整形二维数组Board表示棋盘,Borad[0][0]使棋盘的左上角方格。 tile是一个全局整形变量,用来表示L形骨牌的编号,初始值为0。 tr:棋盘左上角方格的行号;tc:棋盘左上角方格的列号; dr:特殊方各所在的行号;dc:特殊方各所在的列号; size:size=2k,棋盘规格为2k×2k。 复杂度分析:T(k)=4k-1=O(4k) 渐进意义下的最优算法,
展开阅读全文
  微传网所有资源均是用户自行上传分享,仅供网友学习交流,未经上传用户书面授权,请勿作他用。
0条评论

还可以输入200字符

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

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

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

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

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

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

收起
展开