写点什么

递归算法的时间复杂度

  • 2020-02-12
  • 本文字数:12183 字

    阅读完需:约 40 分钟

递归算法的时间复杂度

递归算法大家应该都不陌生吧,其实最开始遇见递归应该是在数学课上,类似于 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 标记它是文件还是文件夹。记录被存下以后,就涉及到取数据的问题了,我们前端需要的目标数据结构是这样的


col 1 | col 2 ------- | ----------------------------------------------------------------------------------------------------------------------------------------------------------------------- 1


                2
3 | `[{``"id"``:1,``"name"``:``"./"``},{``"id"``:2,``"name"``:``"./1.txt"``},`
`{``"id"``:3,``"name"``:``"./dir1/"``},`
`{``"id"``:4,``"name"``:``"./dir1/2.txt"``},...]`
有点类似linux系统的tree命令。 </section> </section> </section></section>
复制代码


第一版代码是这样的:


            </section>        </section>
<section> <section> col 1 | col 2 ----------------------------------------------------------------------------- | --------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22 | `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`
`}`
`)` </section> </section> </section></section>
复制代码


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


第二版代码:


col 1 | col 2 ------------------------------------------------------------- | ----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- 1


                2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18 | `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})`

</section> </section>
<section> <section></section> </section> </section></section>
复制代码


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


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


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


            </section>        </section>    </section></section>
复制代码


col 1col 2


1


2


3


4 | 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 已经求过,多了两步重复计算。


下面是优化的代码:


            </section>        </section>
<section> <section> col 1 | col 2 ------------- | ----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- 1
2
3
4
5 | `fibMap = {1:1,2:2}`
`def fibSquence(n):`
` ``else``:`
` ``result = fibSquence(n-1)+ fibSquence(n-2) fibMap.update({n:result})`
` ``return` `result` </section> </section> </section></section>
复制代码


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


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


            </section>        </section>
<section> <section> col 1 | col 2 ---------------- | ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- 1
2
3
4
5
6 | `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]` </section> </section> </section></section>
复制代码


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


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


本文转载自宜信技术学院网站。


原文链接:http://college.creditease.cn/detail/189


2020-02-12 15:29743

评论

发布
暂无评论
发现更多内容
递归算法的时间复杂度_文化 & 方法_杨轶_InfoQ精选文章