还剩37页未读,继续阅读
本资源只提供10页预览,全部文档请下载后查看!喜欢就下载吧,查找使用更方便
文本内容:
递归与分治策略汇报人递归与分治策略的比添加目录标题较与联系0104递归的概念与原理递归算法的实例分析0205目录分治策略的概念与原分治策略的实例分析理0306添加章节标题递归的概念与原理递归的定义递归是一种编递归过程包括递归基是递归递归的优点是可以将复杂问题分程技巧,通过两个部分递结束的条件,解为简单问题,函数或方法调归基和递归调递归调用是函缺点是容易导致用自身来实现用数或方法调用栈溢出和效率低问题求解自身的过程下递归的原理递归是一种编程技递归的基本思想是递归函数必须有一递归函数必须有一递归函数必须保证巧,通过函数调用将一个大问题分解个或多个基本情况,个或多个递归情况,在有限的步骤内结自身来实现问题求为若干个规模更小即不需要递归就能即通过调用自身来束,即必须有一个解的子问题直接求解的情况求解的情况终止条件递归的分类直接递归函数直接调用自身指数递归递归深度为O2^n间接递归函数通过其他函数间接调用尾递归递归调用在最后一行,可以优自身化为循环非尾递归递归调用不在最后一行,无线性递归递归深度为On法优化为循环递归的应用场景树形数据结构的处理如数学问题的求解如阶乘、排序算法如快速排序、二叉树、多叉树等斐波那契数列等归并排序等图形处理如绘制分形图程序设计如递归函数、操作系统如进程调度、形、处理图像等递归算法等内存管理等分治策略的概念与原理分治策略的定义分治策略是一种将问题分解为若干个子问题,分别求解,然后将子问题的解合并,得到原问题的解的策略分治策略的核心思想是将大问题分解为小问题,小问题再分解为更小的问题,直到问题规模小到可以直接求解分治策略的适用条件是问题可以分解为若干个规模较小的子问题,子问题之间相互独立,子问题的解可以合并得到原问题的解分治策略的优点是可以将大问题分解为小问题,降低问题的复杂度,提高求解效率分治策略的原理分治策略是一种将大问题分解为小问题,分别求解,最后合并求解结果的策略分治策略的核心思想是将一个问题分解为若干个规模更小的子问题,然后分别求解这些子问题,最后将子问题的解合并得到原问题的解分治策略的适用条件是问题可以分解为规模更小的子问题,且子问题的解可以合并得到原问题的解分治策略的优点是可以降低问题的复杂度,提高求解效率分治策略的分类直接分治递归分治动态规划贪心算法分支限界法将问题直接将问题分解将问题分解将问题分解将问题分解分解为若干为若干个子为若干个子为若干个子为若干个子个子问题,问题,然后问题,然后问题,然后问题,然后然后分别求递归求解动态规划求贪心求解分支限界求解解解分治策略的应用场景l快速排序将数组分为两部分,分别排序,然后合并l归并排序将数组分为两部分,分别排序,然后合并l二分查找将数组分为两部分,分别查找,然后合并l矩阵乘法将矩阵分为四部分,分别计算,然后合并l图的遍历将图分为两部分,分别遍历,然后合并l字符串匹配将字符串分为两部分,分别匹配,然后合并递归与分治策略的比较与联系递归与分治策略的相似之处都是一种解决问题的方法都可以将大问题分解为小都可以重复使用相同的算都可以降低问题的复杂度问题法递归与分治策略的不同之处分治将问题递归通过函递归需要栈分治需要额递归容易理分治效率较分解为多个子数调用自身来空间来保存函外的空间来存解,实现简单,高,但实现较问题,分别解解决问题,适数调用信息,储子问题的解,但效率较低为复杂,需要决后再合并结用于解决具有果,适用于解可能导致栈溢可能导致空间良好的算法设决规模较大的重复性的问题出复杂度较高计能力问题递归与分治策略的联系递归与分治策略都是解决问题的有效方法递归与分治策略都可以将大问题分解为小问题递归与分治策略都可以通过解决小问题来解决大问题递归与分治策略都可以提高解决问题的效率递归与分治策略的转换关系l递归通过函数调用自身来解决问题,适用于解决可分解为多个相同子问题的问题l分治将问题分解为多个子问题,分别求解,最后合并结果,适用于解决可分解为多个不同子问题的问题l转换关系递归可以转换为分治,分治也可以转换为递归,具体取决于问题的性质和求解策略l应用场景递归适用于求解树形结构、图论等问题,分治适用于求解排序、查找等问题递归算法的实例分析阶乘的递归算法递归定义n的阶乘定义为n乘以n-1的阶乘,直到n=1为止递归公式n!=n*n-1!递归实现使用递归函数实现阶乘计算递归终止条件n=1时返回1,否则返回n*n-1!斐波那契数列的递归算法斐波那契数列的定义一个数列,其中每个数字是前两个数字的和,例如0,1,1,2,3,5,8,13,...递归算法通过递归函数实现斐波那契数列的生成,例如fn=fn-1+fn-2递归算法的实现通过递归函数实现斐波那契数列的生成,例如fn=fn-1+fn-2递归算法的时间复杂度O2^n,因为每个数字都需要计算两次二叉树遍历的递归算法递归定义二叉树遍历是指从根节点开始,按照中序遍历先访问左子树,然后访问根某种顺序访问二叉树中的所有节点,且每个节点节点,最后访问右子树只访问一次后序遍历先访问左子树,然后访问右递归算法二叉树遍历的递归算法通常采用先序遍历、中序遍历和后序遍历三种方式子树,最后访问根节点递归实现递归算法实现二叉树遍历时,需要定先序遍历先访问根节点,然后访问左义递归函数,并在递归函数中实现对当前节点的子树,最后访问右子树访问和递归调用排序算法中的递归应用快速排序通过递归方式实现快速排序算法归并排序通过递归方式实现归并排序算法堆排序通过递归方式实现堆排序算法桶排序通过递归方式实现桶排序算法分治策略的实例分析归并排序的分治策略归并排序是一种分治策略的典型应用分治策略将大问题分解为小问题,归并排序将数组分为两部分,分别排序归并排序通过递归实现,每次递归将数组分为两部分,然后合并归并排序的时间复杂度为Onlogn,是一种高效的排序算法快速排序的分治策略l基本思想将序列分为两部分,一部分小于等于基准,另一部分大于基准l操作步骤选取一个基准元素,将序列分为两部分,然后对两部分分别进行快速排序l时间复杂度Onlognl空间复杂度Onl适用场景适用于数据量较大的排序问题分区切割问题的分治策略问题描述将一分区方法采用递归过程不断合并结果将划个大矩形区域划递归方法,将大将小矩形区域划分后的小矩形区分为若干个小矩矩形区域划分为分为更小的矩形域合并为一个大形区域两个相等的小矩区域,直到无法矩形区域,得到形区域再分最终结果动态规划中的分治策略l动态规划一种解决最优化问题的方法,通过将问题分解为更小的子问题来解决l分治策略将问题分解为更小的子问题,分别求解,然后合并结果l动态规划中的分治策略将问题分解为更小的子问题,分别求解,然后合并结果,形成最优解l实例分析背包问题、最短路径问题等,通过动态规划中的分治策略求解总结与展望递归与分治策略的重要性和意义l提高效率通过将大问题分解为小问题,可以大大提高解决问题的效率l降低复杂度通过递归和分治策略,可以将复杂问题简化为简单问题,降低问题的复杂度l提高可扩展性递归和分治策略可以大大提高算法的可扩展性,使其能够处理大规模问题l提高稳定性递归和分治策略可以大大提高算法的稳定性,使其能够处理各种类型的问题递归与分治策略在实际问题中的应用前景问题规模适用于大规模、复杂问题的求解计算效率提高计算效率,降低时间复杂度应用领域广泛应用于计算机科学、数学、物理等领域发展趋势随着计算机技术的发展,递归与分治策略的应用前景将更加广阔对递归与分治策略未来研究的展望深入研究进一步研究递归与分治策略的理论基础和应用场景优化算法提高递归与分治策略的效率和稳定性跨学科应用探索递归与分治策略在其他领域的应用创新研究开发新的递归与分治策略,解决更复杂的问题感谢您的观看汇报人。