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

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

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