专栏首页宜信技术实践递归算法的时间复杂度

递归算法的时间复杂度

递归算法应该都不陌生,其实最开始遇见递归应该是在数学课上,类似于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]

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

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

作者:杨轶

来源:宜信技术学院

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 【集合详解】ArrayList 源码解读之动态扩容

    ArrayList 是一个 Java 集合,它的底层数据结构实际上就是一个数组,只不过这个数组长度不固定,动态可变,其中数组元素的类型是 Object 类型的,...

    周三不加班
  • JAVA设计模式之单例模式

    概念:java中单例模式是一种常见的设计模式,单例模式的写法有好几种,这里主要介绍三种:懒汉式单例、饿汉式单例、登记式单例。

    秃头哥编程
  • 一文看懂 FM ( Factorization Machine ) 模型的各种变式

    FM 模型最早由 Steffen Rendle 在2010年提出,解决了稀疏数据场景下的特征组合问题,在广告、推荐等领域被广泛使用。FM 模型简单而且效果好,可...

    石晓文
  • 简述 JVM 垃圾回收算法

    之前我们学习了 JVM 基本介绍 以及 什么样的对象需要被 GC ?,今天就来学习一下 JVM 在判断出一个对象需要被 GC 会采用何种方式进行 GC。在学习 ...

    周三不加班
  • 高并发的中断下半部tasklet实例解析

    最近为了解决一个技术问题,需要用到内核里中断下半部的tasklet机制,使用过程遇到了非常有趣的问题。在解决问题过程中,也逐步加深了对tasklet机制的理解。...

    Linux阅码场
  • 关于后端统一数据格式的一点总结

    最近在学SpringBoot的时候,偶然又看到了统一数据格式这一块的内容,所有打算写点东西总结一下。

    秃头哥编程
  • 推荐几个在线编程学习的网站,程序员必备

    首先推荐的当然是github。作为全球最大的同性交友网站,这里聚集了大量优秀的程序员和源码项目。github是一个面向开源和私人软件项目的托管平台,作为开源代码...

    秃头哥编程
  • 李宏毅:1 天搞懂深度学习,我总结了 300 页 PPT(附思维导图)

    https://blog.csdn.net/u010164190/article/details/72633245

    石晓文
  • Github项目推荐 | visdat - 数据初步探索性可视化工具

    visdat - Preliminary Exploratory Visualisation of Data

    AI研习社
  • 【ES6基础】Object的新方法

    Object对象可谓是JS的重要核心内容,在你使用JS的过程中,你会发现自己的工作大部分都是在操作对象,ES6、ES7、ES8引入了不少新的方法,本篇文章笔者将...

    前端达人

扫码关注云+社区

领取腾讯云代金券