分治法概念:
分治法:将原问题分成n个规模较小而结构与原问题相似的子问题;递归地解这些子问题,然后合并其结果就得到原问题的解。
分治模式在每一层递归上都有三个步骤:
第一步:将原问题分解成一系列子问题;(分解)
第二部:递归地解各子问题。若子问题足够小,则直接求解;(解决)
第三部:将子问题的结果合并成原问题的解;(合并)
分治法算法分析:
当一个算法中含有对自身的递归调用时,其运行时间可用一个递归方程来表述,分治算法中的递归式是基于基本模式中的三个步骤的。设T(n)为在规模n下问题的运行时间。如果n足够小,例如有n<c(c为常量),则得到它的直径解的时间为常量,写作theta(1)。假设我们把原问题分成a个子问题,每一个的大小是原问题的1/b。若分解该问题和合并解的时间各为D(n),则得递归式:
theta(1) 若n<=c
T(n)={
aT(n/b)+D(n)+C(n) 否则
合并排序算法的分析:
合并算法是分治法的一种,故基本步骤如下:
分解:这一步仅仅是计算出子数组中间位置,因而D(n)=theta(1)
解决:递归地解两个规模为n/2的子问题,时间为2T(n/2)
合并:已知merge过程在一个含有n个元素的子数组上的运行时间为theta(n)。则C(n)=theta(n).
函数D(n)和C(n)的阶为theta(n)和theta(1),他们的和是n的线性函数,即阶为theta(n)。将它与“解决”步骤所得的项2T(n/2),即得T(n)的递归表示:
theta(1) 若n=1
T(n)={
2T(n/2)+theta(n) 若n>1
递归式解法:
本来打算详细讲解的,但是由于时间有限,直接在网上找到一份ppt上传吧,基本上能讲清楚,而且PPT格式比网页看起来更友好些,各位看官见谅
分享到:
相关推荐
深入理解分治法的算法思想,应用分治法解决实际的算法问题。 【实验性质】 验证性实验(学时数:2H) 【实验内容与要求】 1、设有n=2k个运动员要进行网球循环赛。现要设计一个满足以下要求的比赛日程表:⑴每个选手...
c语言分治法求众数重数-五大常见算法策略之——递归与分治策略,算法数据结构 五大常用算法
MIT算法导论公开课之课程笔记 分治法.rar
关于分治法的算法结课论文,讲述了分治法与递归的联系与区别。分治法是解题思路,而递归是实现的方法,可用递归,也可用非递归
递归与分治策略是学习计算机算法设计与分析的基础,掌握了这样的思想才能良好地高效率地去解决一些问题
2、修订了递归式(现在称为“分治策略”)那一章的内容,更广泛地覆盖分治法。 3、移除两章很少讲授的内容:二项堆和排序网络。 4、修订了动态规划和贪心算法相关内容。 5、流网络相关材料现在基于边上的全部流。 6...
算法分析与设计课程作业,递归与分治C代码,可以运行的代码
算法思想——递归与分治 算法思想——递归与分治
递归与分治实验(二)Problem A:再次Hanoi塔问题Problem B:输油管道问题Problem C:Integer FactorizationProblem D:邮局选址问题Problem E:Gray code
java 快速排序 折半查找的界面实现 (递归与分治法)
常用的算法设计技术有迭代法、穷举搜索法、递推法、贪婪法、回溯法、分治法和动态规划法等。另外,为了以更简洁的形式设计和描述算法,在设计算法时常采用递归技术,用递归描述算法。 本讲中,主要介绍分治法。
这是递归与分治法算法设计的实验报告,内附可运行代码!
本程序包括递归与分治算法章节课后习题中的内容的集合,方便简单易懂,对刚学算法的人帮助很大,这是我们这学期的三道作业题合在一起的程序。
递归与分治,基本的算法基础,希望对大家有帮助。
在一个2的k次方乘以2的k次方个方格的棋盘中,恰有一个方格与其他方格不同为特殊方格,棋盘称为特殊棋盘,用4种不同形态的L型骨牌覆盖给定的特殊棋盘上除特殊方格以外的所有方格,且任何2个L型骨牌不得重叠覆盖。
算法设计 蛮力法 分治法 动态规划 贪心算法 分支限界法 回溯法 近似算法 减制法
递归小结 •优点:结构清晰,可读性强,而且容易用数学归纳法来证明算法的正确性,因此它为设计算法、调试程序带来很大方便。 •缺点:递归算法的运行效率较低,无论是耗费的计算时间还是占用的存储空间都比非递归...
这是有关算法的知识,分治法的基本思想 在分治法中,子问题的解法通常与原问题相同,自然导致递归过程
里面包含了2个全排列的算法 一个是:分治法求解全排列 另一个是:回溯法求全排列