递归算法时间复杂度(递归算法时间复杂度例题)

2023-11-09 0 746

递归算法时间复杂度(递归算法时间复杂度例题)

1、递归算法应该都不陌生,其实最开始遇见递归应该是在数学课上,类似于()=(-1)+(+1),(1)=1,(2)=4,(3)=3这种数学题大家应该见过不少,其实思想就是层层递归,最终将目标值用(1),(2),(3)表示。之前做了一个需求,需要实现类似操作系统文件夹的功能,我们用数据库记录数据,表字段有4列,分别是,_,_,_记录文件或文件的名字,记录它的父级,_标记它是文件还是文件夹。记录被存下以后,就涉及到取数据的问题了,我们前端需要的目标数据结构是这样的:。有点类似系统的命令。

2、第一版代码是这样的:。大概看一下这个算法的时间复杂度,第一层的遍历时间复杂度是,第二层遍历的时间复杂度是,内层的时间复杂度是,^2,再加上递归,最后的时间复杂度是,2^*^2,这个算法可见很粗糙,假如递归深度到是100,最后执行效率简直会让人头皮发麻。接下来我们考虑一下如何优化。

3、我们用变量保存每一次的,这次我们看看时间复杂度是多少。第一层遍历时间复杂度是(),加上递归,最后的时间复杂度是(2^*),不算太理想,最起码比第一次好点。

4、再看看一个面试的常见的题目,斐波拉契数列,=1,1。求第位是多少。一看首先就想到了递归的方式:。

5、这个算法的时间复杂度是(2^),关于时间复杂度具体看调用次数便能明白。我们考虑一下如何优化,比如求=3是,需要先求=2,=1,但是最开始=1,=2已经求过,多了两步重复计算。下面是优化的代码:。

递归算法时间复杂度(递归算法时间复杂度例题)

1、我们用报存中间值,是基于实现的,时间复杂度是(1),这样这个算法的时间复杂度就是()。但是事实上这个问题大可不必用递归方式求解。这样我们只用一次遍历,便可以求出目标值。递归算法的优化大概就是避免重复运算,将中金状态保存起来,以便下次使用,从结构上来看,是将时间复杂度转换为空间复杂度来解决。

2、递归算法的效率其实是非常低的,能不用递归就尽量不用递归;当然了也要具体问题具体对待,比如说开始提到我做的项目遇到的问题,不用递归我还真想不出其他更好的方式解决。来源:宜信技术学院。

本站所有资源版权均属于原作者所有,这里所提供资源均只能用于参考学习用,请勿直接商用。若由于商用引起版权纠纷,一切责任均由使用者承担。

米库模板-苹果cms模板 其他教程 递归算法时间复杂度(递归算法时间复杂度例题) https://www.mikucms.com/23645.html

常见问题

相关文章