还剩21页未读,继续阅读
本资源只提供10页预览,全部文档请下载后查看!喜欢就下载吧,查找使用更方便
文本内容:
《递归与搜索上》ppt课件•递归概述•递归算法•递归与栈•搜索算法•递归与搜索的应用01递归概述递归的定义递归是指在函数或算法中直接它通过将问题分解为更小的子递归的基本思想是将复杂问题或间接调用自身的一种方法问题来解决,子问题的求解过转化为简单问题来解决程与原问题相同递归的基本思想01020304递归的基本思想是将问题分解然后通过子问题的解来构建原分解是将原问题分解为更小的递归的基本思想包括两个主要为更小的子问题,直到子问题问题的解子问题,组合是将子问题的解步骤分解和组合可以简单地直接求解组合起来得到原问题的解递归的分类根据递归的性质,可以将递归分直接递归是指函数或算法直接调间接递归是指函数或算法通过调为两类直接递归和间接递归用自身来解决问题用其他函数或算法间接地调用自身来解决问题02递归算法阶乘递归算法阶乘递归算法01阶乘递归算法是一种常见的递归算法,用于计算一个正整数的阶乘阶乘是一个数与比它小的所有正整数的乘积例如,5的阶乘(记作5!)是5*4*3*2*1=120递归步骤02阶乘递归算法的递归步骤包括将问题分解为更小的子问题(例如,计算n的阶乘可以分解为计算n-1的阶乘),然后使用这些子问题的解来解决原始问题时间复杂度03阶乘递归算法的时间复杂度是指数级的,因为每个问题都可能导致大量的子问题因此,对于较大的输入,阶乘递归算法可能会变得非常慢斐波那契数列递归算法斐波那契数列递归步骤时间复杂度斐波那契数列是一个无穷整数序斐波那契数列递归算法的递归步斐波那契数列递归算法的时间复列,其中每个数字是前两个数字骤包括使用前两个数字来计算下杂度也是指数级的,因为对于较的和序列的前几个数字是
0、
1、一个数字例如,要计算第n个大的输入,该算法会涉及大量的
1、
2、
3、
5、
8、13等斐波那契数,可以使用第n-1和重复计算第n-2个斐波那契数汉诺塔递归算法递归步骤汉诺塔递归算法的递归步骤包括将问题分解为更小的子问题(例如,将一组盘子从一个柱子移动到中间柱子),然后使用这些子问题的解来解决原始问题时间复杂度汉诺塔问题的最坏情况时间复杂度是O2^n,其中n是盘子的数量这是因为对于每个盘子,都存在两个移动的选择,并且这些选择是相互排斥的03递归与栈栈的基本概念栈是一种后进先出栈具有两个主要操作(LIFO)的数据结构,压栈(push)和弹用于存储数据的列表栈(pop)栈中的数据只能从一端(称为栈顶)添加或移除递归与栈的关系递归函数在执行过程中会使用栈来保当函数返回时,其局部变量和参数从存函数调用时的状态栈中弹出,恢复到调用前的状态当函数被调用时,它的参数和局部变量会被压入栈中,以便在函数返回时恢复执行递归调用的执行过程递归函数在执行时,首先将当前函数调用信息(如参数、局部变量等)压入栈中然后进入递归调用的执行过程,直到遇到返回语句或递归终止条件在返回时,从栈中弹出之前保存的函数调用信息,恢复到调用前的状态,并继续执行后续代码04搜索算法线性搜索算法010203线性搜索算法时间复杂度适用场景从列表的第一个元素开始,On,其中n是列表的长当列表较小且未排序时,逐个检查每个元素,直到度线性搜索算法是简单且有找到目标元素或遍历完整效的个列表二分搜索算法二分搜索算法在已排序的列表中,每次比较中间元素与目标元素,根据比较结果决定搜索区间,不断缩小搜索范围,直到找到目标元素或搜索区间为空时间复杂度Olog n,其中n是列表的长度适用场景当列表较大且已排序时,二分搜索算法具有较高的效率深度优先搜索算法深度优先搜索算法按照深度优先的顺序遍历图或树结构,尽可能深地搜索树的分支,当节点v的所在边都己被探寻过,搜索将回溯到发现节点v的那条边的起始节点时间复杂度On,其中n是图或树的节点数适用场景用于遍历或搜索树或图结构,适用于具有层次结构的数据集05递归与搜索的应用排序算法中的递归与搜索快速排序归并排序堆排序使用递归进行分区和比较,递归地将数组分解为更小通过构建最大堆或最小堆,通过搜索分区内的元素来的子数组,然后合并已排然后依次取出堆顶元素,达到排序的目的序的子数组来得到最终的再调整堆,实现排序排序结果分治算法中的递归与搜索二分查找在有序数组中,通过不断将搜索范合并排序围缩小一半来找到目标元素采用分治策略,递归地将数组分解为更小的子数组,然后合并已排序的子数组来得到最终的排序结果矩阵乘法利用分治策略,将矩阵乘法转化为多个小规模的矩阵乘法问题,然后递归地求解这些小问题数据结构中的递归与搜索树哈希表树是一种常见的数据结构,哈希表是一种基于哈希函数可以通过递归的方式遍历树的数据结构,可以通过哈希的节点,如前序遍历、中序函数计算出元素在哈希表中遍历和后序遍历的位置,然后进行搜索和插入操作图图是一种复杂的数据结构,可以通过深度优先搜索(DFS)或广度优先搜索(BFS)进行遍历DFS使用递归实现,BFS则使用队列实现THANKS感谢观看。