《算法设计与分析》-第二章-递归与分治17103课件.ppt
- 【下载声明】
1. 本站全部试题类文档,若标题没写含答案,则无答案;标题注明含答案的文档,主观题也可能无答案。请谨慎下单,一旦售出,不予退换。
2. 本站全部PPT文档均不含视频和音频,PPT中出现的音频或视频标识(或文字)仅表示流程,实际无音频或视频文件。请谨慎下单,一旦售出,不予退换。
3. 本页资料《《算法设计与分析》-第二章-递归与分治17103课件.ppt》由用户(三亚风情)主动上传,其收益全归该用户。163文库仅提供信息存储空间,仅对该用户上传内容的表现方式做保护处理,对上传内容本身不做任何修改或编辑。 若此文所含内容侵犯了您的版权或隐私,请立即通知163文库(点击联系客服),我们立即给予删除!
4. 请根据预览情况,自愿下载本文。本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
5. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007及以上版本和PDF阅读器,压缩文件请下载最新的WinRAR软件解压。
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 算法设计与分析 算法 设计 分析 第二 递归 分治 17103 课件
- 资源描述:
-
1、算法设计与分析算法设计与分析- -第二章第二章 递归递归与分治与分治1710317103第二章第二章 递归与分治递归与分治l2.1 分治法的基本思想l2.2 分治法的适用条件l2.3 分治法的基本步骤l2.4 分治法的应用2.1 分治法(分治法(divide-and-conquer)的基本)的基本思想思想l为求解大问题,可以:分割成k个更小规模的子问题。对这k个子问题分别求解。如果子问题的规模仍然不够小,则再划分为k个子问题,如此递归的进行下去,直到问题规模足够小,很容易求出其解为止。将求出的小规模的问题的解合并为一个更大规模的问题的解,自底向上逐步求出原来问题的解。l将要求解的较大规模的问题
2、分割成k个更小规模的子问题。2.1 分治法的基本思想分治法的基本思想nT(n/2)T(n/2)T(n/2)T(n/2)T(n)= l对这k个子问题分别求解。如果子问题的规模仍然不够小,则再划分为k个子问题,如此递归的进行下去,直到问题规模足够小,很容易求出其解为止。l对这k个子问题分别求解。如果子问题的规模仍然不够小,则再划分为k个子问题,如此递归的进行下去,直到问题规模足够小,很容易求出其解为止。nT(n)=n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n
3、/4)T(n/4)T(n/4)2.1 分治法的基本思想分治法的基本思想l将求出的小规模的问题的解合并为一个更大规模的问题的解,自底向上逐步求出原来问题的解。nT(n)=n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)2.1 分治法的基本思想分治法的基本思想nT(n)=n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)n
4、/2T(n/4)T(n/4)T(n/4)T(n/4)2.1 分治法的基本思想分治法的基本思想l将求出的小规模的问题的解合并为一个更大规模的问题的解,自底向上逐步求出原来问题的解。分治法的设计思想是,将一个难以直接解决的大分治法的设计思想是,将一个难以直接解决的大问题,分割成一些规模较小的相同问题,以便各问题,分割成一些规模较小的相同问题,以便各个击破,分而治之。个击破,分而治之。2.1 分治法的基本思想分治法的基本思想2.1 分治法的基本思想分治法的基本思想2.2 分治法的适用条件分治法的适用条件l该问题的规模缩小到一定的程度就可以容易地解决;该问题的规模缩小到一定的程度就可以容易地解决;l该
5、问题可以分解为若干个规模较小的相同问题,即该该问题可以分解为若干个规模较小的相同问题,即该问题具有问题具有最优子结构性质最优子结构性质l利用该问题分解出的子问题的解可以合并为该问题的利用该问题分解出的子问题的解可以合并为该问题的解;解;l该问题所分解出的各个子问题是相互独立的,即子问该问题所分解出的各个子问题是相互独立的,即子问题之间不包含公共的子问题。题之间不包含公共的子问题。 2.3 分治法的基本步骤分治法的基本步骤divide-and-conquer(P) if ( | P | = n0) adhoc(P); /解决小规模的问题 divide P into smaller subinst
6、ances P1,P2,.,Pk;/分解问题 for (i=1,i1时,perm(R)由(r1)perm(R1),(r2)perm(R2),(rn)perm(Rn)构成。 2.4 分治法的应用分治法的应用全排列算法全排列算法lvoid perm(int list, int k, int m) l/产生listk.m的所有排列l/其中list0.k-1是前缀,后缀是listk.ml/调用perm(list,0,n-1)则产生list0.n-1的全排列lif (k=m)l For (i=0;i=m;i+)l Printf(“%d ”,listi);l Printf(“n”);llelsel For
7、(i=k;i=m;i+)l Swap(listk,listi);l Perm(list,k+1,m);l Swap(listk,listi);l ll例例3 给定已按升序排好序的给定已按升序排好序的n个元素个元素a0:n-1,现要在这,现要在这n个个元素中找出一特定元素元素中找出一特定元素x。分析:分析:该问题的规模缩小到一定的程度就可以容易地解决;该问题的规模缩小到一定的程度就可以容易地解决;该问题可以分解为若干个规模较小的相同问题该问题可以分解为若干个规模较小的相同问题;分解出的子问题的解可以合并为原问题的解;分解出的子问题的解可以合并为原问题的解;分解出的各个子问题是相互独立的。分解出的
8、各个子问题是相互独立的。 2.4 分治法的应用分治法的应用二分搜索算法二分搜索算法:int binarySearch(int a, int x, int n) left = 0; right = n - 1; while (left amiddle) left = middle + 1; else right = middle - 1; return -1; / 未找到x l例例3 2.4 分治法的应用分治法的应用A和B的乘积矩阵C中的元素Ci,j定义为: nkjkBkiAjiC1u传统方法:O(n3)l例例4 2.4 分治法的应用分治法的应用使用与上例类似的技术,将矩阵A,B和C中每一矩阵都
9、分块成4个大小相等的子矩阵。由此可将方程C=AB重写为:u分治法:222112112221121122211211BBBBAAAACCCC由此可得:2112111111BABAC2212121112BABAC2122112121BABAC2222122122BABAC复杂度分析复杂度分析T(n)=O(n3) 没有改进没有改进22)()2/(8) 1 ()(2nnnOnTOnTu改进:为了降低时间复杂度,必须减少乘法的次数。222112112221121122211211BBBBAAAACCCC)(2212111BBAM2212112)(BAAM1122213)(BAAM)(1121224BBA
展开阅读全文