递归算法的时间复杂度
递归算法应该都不陌生,其实最开始遇见递归应该是在数学课上,类似于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]
这样我们只用一次遍历,便可以求出目标值。
递归算法的优化大概就是避免重复运算,将中金状态保存起来,以便下次使用,从结构上来看,是将时间复杂度转换为空间复杂度来解决。递归算法的效率其实是非常低的,能不用递归就尽量不用递归;当然了也要具体问题具体对待,比如说开始提到我做的项目遇到的问题,不用递归我还真想不出其他更好的方式解决。
作者:杨轶
来源:宜信技术学院
免责声明:
① 本站未注明“稿件来源”的信息均来自网络整理。其文字、图片和音视频稿件的所属权归原作者所有。本站收集整理出于非商业性的教育和科研之目的,并不意味着本站赞同其观点或证实其内容的真实性。仅作为临时的测试数据,供内部测试之用。本站并未授权任何人以任何方式主动获取本站任何信息。
② 本站未注明“稿件来源”的临时测试数据将在测试完成后最终做删除处理。有问题或投稿请发送至: 邮箱/279061341@qq.com QQ/279061341