写点什么

递归算法的时间复杂度

  • 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:29736

评论

发布
暂无评论
发现更多内容

基于多尺度图神经网络的流场预测,实现精度与速度的平衡

飞桨PaddlePaddle

人工智能 百度 paddle 飞桨 百度飞桨

业财一体,精细管控丨华为云SparkPack助力成长型企业数字化转型

YG科技

在 Go 中如何实现类似 Python 中的 with 上下文管理器

江湖十年

Go 后端

福昕软件与国广传媒达成战略合作,共促AI技术创新发展

新消费日报

华为云SparkPack:成长型企业的数字化转型利器

YG科技

2023-07-02:给定一个1~N的排列,每次将相邻两数相加,可以得到新的序列,长度是N-1 再对新的序列,每次将相邻两数相加,可以得到新的序列,长度是N-2 这样下去可以最终只剩一个数字 比如 :

福大大架构师每日一题

Go 福大大架构师每日一题

大厂月入3w+,失业焦虑折磨着我

程序员晚枫

程序员 大厂 焦虑

从低谷逆转,数字化转型企业可以信任华为云SparkPack

YG科技

红队攻防之快速打点

权说安全

网络攻防

C++实现对RGB图片进行编码

芯动大师

ChatGLM2-6B环境搭建

IT蜗壳-Tango

传统网络环境应付不了企业发展需求,华为云下载加速解决方案体验如何?

YG科技

落地领域大模型应知必会 (1) :主要微调方法总览

Baihai IDP

人工智能 白海科技 大语言模型 大模型微调 领域大模型

WebAssembly:让Istio变得更强大

谐云

istio WebAssenbly

AI、机器学习、大模型、生成式AI和安全

啸天

人工智能 机器学习 安全 大模型 ChatGPT

代码随想录训练营Day04 - 链表(下)

jjn0703

一文讲透 Redis 事务 (事务模式 VS Lua 脚本)

高端章鱼哥

lua redis vs

云原生MYSQL数据库架构分享

谐云

MySQL 云原生

什么是WebAssembly及其必要性

谐云

WebAssenbly

98位企业技术高管入学百度AICA 大模型带来AI人才三大能力要求

飞桨PaddlePaddle

人工智能 百度 paddle 百度飞桨

IoTLink版本更新V1.34.0

山东云则信息科技

Java Vue 后端 物联网 前段

什么是KubeEdge?

谐云

kuberedge kurbernetes

MySQL笔记之Checkpoint机制

互联网工科生

MySQL 高可用 CheckPoint

浅谈kubernetes存储—glusterfs故障排查

谐云

kuberedge

华为云下载加速解决方案:让您的下载更快更稳定

YG科技

“科创中国”大湾区青年百人会论坛成功举办

飞桨PaddlePaddle

人工智能 百度 paddle 百度飞桨

代码随想录训练营Day03- 链表(上)

jjn0703

基于eBPF技术的可观测实践探索

谐云

云原生

边阅读,边成长

少油少糖八分饱

阅读 每天读本书 书评

递归算法的时间复杂度_文化 & 方法_杨轶_InfoQ精选文章