递归算法的时间复杂度

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了递归算法的时间复杂度，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含3298字，纯文字阅读大概需要5分钟。

内容图文

递归算法应该都不陌生，其实最开始遇见递归应该是在数学课上，类似于f(x)=f(x-1)+f(x+1)，f(1)=1，f(2)=4，f(3)=3这种数学题大家应该见过不少，其实思想就是层层递归，最终将目标值用f(1)，f(2)，f(3)表示。

之前做了一个需求，需要实现类似操作系统文件夹的功能，我们用MySQL数据库记录数据，表字段有4列，分别是id，index_name，pid，is_directory，index_name记录文件或文件的名字，pid记录它的父级id，is_directory标记它是文件还是文件夹。

记录被存下以后，就涉及到取数据的问题了，我们前端需要的目标数据结构是这样的：

[{"id":1,"name":"./"},{"id":2,"name":"./1.txt"},
{"id":3,"name":"./dir1/"},
{"id":4,"name":"./dir1/2.txt"},...]

有点类似linux系统的tree命令。

第一版代码是这样的：

tree = []
def getTree(pid):
              return
for index in childIndexes:
 if len(tree) == 0:
   if index.is_directory==1                            tree.append(
{'id':index.id,'name':'./'+index.index_name+'/'})                     
getTree(index.id)
                     else:                            
tree.append(
{'id':index.id,'name':'/'+index.index_name})
              else: 
                    for item in tree:  
if item['id'] == index.id
                                   if item.is_directory==1:                                          tree.append({'id':index.id,'name': 
item['name']+index.index_name+'/'})    
                               else:  
                                        tree.append
(
{'id':index.id,'name':item['name']+index.index_name
}
)

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

第二版代码：

tree = []
def getTree(pid,path='./'):
              return
       for index in childIndexes:
             if len(tree) == 0: 
                    if index.is_directory==1                            tree.append({'id':index.id,
'name':path+index.index_name+'/'}) 
                           getTree(index.id, 
path+index.index_name+'/')
                    else:
                           tree.append({'id':index.id,
'name':path+index.index_name}) 
             else: 
                    if item.is_directory==1:                            tree.append({'id':index.id,
'name':path+index.index_name+'/'})
                     else: 
                           tree.append({'id':index.id,
'name':path+index.index_name})

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

再看看一个面试的常见的题目，斐波拉契数列，n=1,1,3,5,8,13...，求第n位是多少？

一看首先就想到了递归的方式：

def fibSquence(n):     
  if n in (1,2):       
   return 
   fibSquence(n-1)+ fibSquence(n-2)

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

下面是优化的代码：

fibMap = {1:1,2:2}
def fibSquence(n):
       else:
        result = fibSquence(n-1)+ fibSquence(n-2)              fibMap.update({n:result})
              return result

我们用map报存中间值，map是基于hash实现的，时间复杂度是O(1)，这样这个算法的时间复杂度就是O(n)。

但是事实上这个问题大可不必用递归方式求解。

fibMap = {1:1,2:2}
def fibSquence(n):
       else:
              for i in range(3,n+1): 
                    fibMap.update({i:fibMap[i-1]+fibMap[i-2]})
              return fibMap[n]

这样我们只用一次遍历，便可以求出目标值。

递归算法的优化大概就是避免重复运算，将中金状态保存起来，以便下次使用，从结构上来看，是将时间复杂度转换为空间复杂度来解决。递归算法的效率其实是非常低的，能不用递归就尽量不用递归；当然了也要具体问题具体对待，比如说开始提到我做的项目遇到的问题，不用递归我还真想不出其他更好的方式解决。

作者：杨轶

来源：宜信技术学院

内容总结

以上是互联网集市为您收集整理的递归算法的时间复杂度全部内容，希望文章能够帮你解决递归算法的时间复杂度所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---