分治算法详解课件.ppt
《分治算法详解课件.ppt》由会员分享,可在线阅读,更多相关《分治算法详解课件.ppt(21页珍藏版)》请在三一办公上搜索。
1、分治,1,将要求解的较大规模的问题分割成k个更小规模的子问题。,算法总体思想,n,T(n/m),T(n/m),T(n/m),T(n/m),T(n),=,对这k个子问题分别求解。如果子问题的规模仍然不够小,则再划分为k个子问题,如此递归的进行下去,直到问题规模足够小,很容易求出其解为止。, ,2,算法总体思想,对这k个子问题分别求解。如果子问题的规模仍然不够小,则再划分为k个子问题,如此递归的进行下去,直到问题规模足够小,很容易求出其解为止。,n,T(n),=,将求出的小规模的问题的解合并为一个更大规模的问题的解,自底向上逐步求出原来问题的解。, ,3,算法总体思想,将求出的小规模的问题的解合并
2、为一个更大规模的问题的解,自底向上逐步求出原来问题的解。,n,T(n),=, ,4,算法总体思想,将求出的小规模的问题的解合并为一个更大规模的问题的解,自底向上逐步求出原来问题的解。,分治法的设计思想是,将一个难以直接解决的大问题,分割成一些规模较小的相同问题,以便各个击破,分而治之。,5,分治法的适用条件,分治法所能解决的问题一般具有以下几个特征:该问题的规模缩小到一定的程度就可以容易地解决;该问题可以分解为若干个规模较小的相同问题,即该问题具有最优子结构性质利用该问题分解出的子问题的解可以合并为该问题的解;该问题所分解出的各个子问题是相互独立的,即子问题之间不包含公共的子问题。,因为问题的
3、计算复杂性一般是随着问题规模的增加而增加,因此大部分问题满足这个特征。,这条特征是应用分治法的前提,它也是大多数问题可以满足的,此特征反映了递归思想的应用,能否利用分治法完全取决于问题是否具有这条特征,如果具备了前两条特征,而不具备第三条特征,则可以考虑贪心算法或动态规划。,这条特征涉及到分治法的效率,如果各子问题是不独立的,则分治法要做许多不必要的工作,重复地解公共的子问题,此时虽然也可用分治法,但一般用动态规划较好。,6,divide-and-conquer(P) if ( | P | = n0) adhoc(P); /解决小规模的问题 divide P into smaller subi
4、nstances P1,P2,.,Pk;/分解问题 for (i=1,i=k,i+) yi=divide-and-conquer(Pi); /递归的解各子问题 return merge(y1,.,yk); /将各子问题的解合并为原问题的解 ,分治法的基本步骤,人们从大量实践中发现,在用分治法设计算法时,最好使子问题的规模大致相同。即将一个问题分成大小相等的k个子问题的处理方法是行之有效的。这种使子问题规模大致相等的做法是出自一种平衡(balancing)子问题的思想,它几乎总是比子问题规模不等的做法要好。,7,分析:如果n=1即只有一个元素,则只要比较这个元素和x就可以确定x是否在表中。因此这
5、个问题满足分治法的第一个适用条件,分析:比较x和a的中间元素amid,若x=amid,则x在L中的位置就是mid;如果xai,同理我们只要在amid的后面查找x即可。无论是在前面还是后面查找x,其方法都和在a中查找x一样,只不过是查找的规模缩小了。这就说明了此问题满足分治法的第二个和第三个适用条件。,分析:很显然此问题分解出的子问题相互独立,即在ai的前面或后面查找x是独立的子问题,因此满足分治法的第四个适用条件。,二分搜索技术,给定已按升序排好序的n个元素a0:n-1,现要在这n个元素中找出一特定元素x。分析:,该问题的规模缩小到一定的程度就可以容易地解决;该问题可以分解为若干个规模较小的相
6、同问题;分解出的子问题的解可以合并为原问题的解;分解出的各个子问题是相互独立的。,8,二分搜索技术,给定已按升序排好序的n个元素a0:n-1,现要在这n个元素中找出一特定元素x。,据此容易设计出二分搜索算法:template int BinarySearch(Type a, const Type,算法复杂度分析:每执行一次算法的while循环, 待搜索数组的大小减少一半。因此,在最坏情况下,while循环被执行了O(logn) 次。循环体内运算需要O(1) 时间,因此整个算法在最坏情况下的计算时间复杂性为O(logn) 。,9,分治法求数组最大值,给定n个元素a0:n-1,现要在这n个元素中找
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 分治 算法 详解 课件
链接地址:https://www.31ppt.com/p-1563624.html