数据结构与算法之美
王争
前Google工程师
立即订阅
71638 人已学习
课程目录
已完结 75 讲
0/4登录后,你可以任选4讲全文学习。
开篇词 (1讲)
开篇词 | 从今天起,跨过“数据结构与算法”这道坎
免费
入门篇 (4讲)
01 | 为什么要学习数据结构和算法?
02 | 如何抓住重点,系统高效地学习数据结构与算法?
03 | 复杂度分析(上):如何分析、统计算法的执行效率和资源消耗?
04 | 复杂度分析(下):浅析最好、最坏、平均、均摊时间复杂度
基础篇 (38讲)
05 | 数组:为什么很多编程语言中数组都从0开始编号?
06 | 链表(上):如何实现LRU缓存淘汰算法?
07 | 链表(下):如何轻松写出正确的链表代码?
08 | 栈:如何实现浏览器的前进和后退功能?
09 | 队列:队列在线程池等有限资源池中的应用
10 | 递归:如何用三行代码找到“最终推荐人”?
11 | 排序(上):为什么插入排序比冒泡排序更受欢迎?
12 | 排序(下):如何用快排思想在O(n)内查找第K大元素?
13 | 线性排序:如何根据年龄给100万用户数据排序?
14 | 排序优化:如何实现一个通用的、高性能的排序函数?
15 | 二分查找(上):如何用最省内存的方式实现快速查找功能?
16 | 二分查找(下):如何快速定位IP对应的省份地址?
17 | 跳表:为什么Redis一定要用跳表来实现有序集合?
18 | 散列表(上):Word文档中的单词拼写检查功能是如何实现的?
19 | 散列表(中):如何打造一个工业级水平的散列表?
20 | 散列表(下):为什么散列表和链表经常会一起使用?
21 | 哈希算法(上):如何防止数据库中的用户信息被脱库?
22 | 哈希算法(下):哈希算法在分布式系统中有哪些应用?
23 | 二叉树基础(上):什么样的二叉树适合用数组来存储?
24 | 二叉树基础(下):有了如此高效的散列表,为什么还需要二叉树?
25 | 红黑树(上):为什么工程中都用红黑树这种二叉树?
26 | 红黑树(下):掌握这些技巧,你也可以实现一个红黑树
27 | 递归树:如何借助树来求解递归算法的时间复杂度?
28 | 堆和堆排序:为什么说堆排序没有快速排序快?
29 | 堆的应用:如何快速获取到Top 10最热门的搜索关键词?
30 | 图的表示:如何存储微博、微信等社交网络中的好友关系?
31 | 深度和广度优先搜索:如何找出社交网络中的三度好友关系?
32 | 字符串匹配基础(上):如何借助哈希算法实现高效字符串匹配?
33 | 字符串匹配基础(中):如何实现文本编辑器中的查找功能?
34 | 字符串匹配基础(下):如何借助BM算法轻松理解KMP算法?
35 | Trie树:如何实现搜索引擎的搜索关键词提示功能?
36 | AC自动机:如何用多模式串匹配实现敏感词过滤功能?
37 | 贪心算法:如何用贪心算法实现Huffman压缩编码?
38 | 分治算法:谈一谈大规模计算框架MapReduce中的分治思想
39 | 回溯算法:从电影《蝴蝶效应》中学习回溯算法的核心思想
40 | 初识动态规划:如何巧妙解决“双十一”购物时的凑单问题?
41 | 动态规划理论:一篇文章带你彻底搞懂最优子结构、无后效性和重复子问题
42 | 动态规划实战:如何实现搜索引擎中的拼写纠错功能?
高级篇 (9讲)
43 | 拓扑排序:如何确定代码源文件的编译依赖关系?
44 | 最短路径:地图软件是如何计算出最优出行路径的?
45 | 位图:如何实现网页爬虫中的URL去重功能?
46 | 概率统计:如何利用朴素贝叶斯算法过滤垃圾短信?
47 | 向量空间:如何实现一个简单的音乐推荐系统?
48 | B+树:MySQL数据库索引是如何实现的?
49 | 搜索:如何用A*搜索算法实现游戏中的寻路功能?
50 | 索引:如何在海量数据中快速查找某个数据?
51 | 并行算法:如何利用并行处理提高算法的执行效率?
实战篇 (5讲)
52 | 算法实战(一):剖析Redis常用数据类型对应的数据结构
53 | 算法实战(二):剖析搜索引擎背后的经典数据结构和算法
54 | 算法实战(三):剖析高性能队列Disruptor背后的数据结构和算法
55 | 算法实战(四):剖析微服务接口鉴权限流背后的数据结构和算法
56 | 算法实战(五):如何用学过的数据结构和算法实现一个短网址系统?
加餐:不定期福利 (6讲)
不定期福利第一期 | 数据结构与算法学习书单
不定期福利第二期 | 王争:羁绊前行的,不是肆虐的狂风,而是内心的迷茫
不定期福利第三期 | 测一测你的算法阶段学习成果
不定期福利第四期 | 刘超:我是怎么学习《数据结构与算法之美》的?
总结课 | 在实际开发中,如何权衡选择使用哪种数据结构和算法?
《数据结构与算法之美》学习指导手册
加餐:春节7天练 (7讲)
春节7天练 | Day 1:数组和链表
春节7天练 | Day 2:栈、队列和递归
春节7天练 | Day 3:排序和二分查找
春节7天练 | Day 4:散列表和字符串
春节7天练 | Day 5:二叉树和堆
春节7天练 | Day 6:图
春节7天练 | Day 7:贪心、分治、回溯和动态规划
加餐:用户学习故事 (2讲)
用户故事 | Jerry银银:这一年我的脑海里只有算法
用户故事 | zixuan:站在思维的高处,才有足够的视野和能力欣赏“美”
结束语 (3讲)
结束语 | 送君千里,终须一别
第2季回归 | 这一次,我们一起拿下设计模式!
打卡召集令 | 60 天攻克数据结构与算法
免费
数据结构与算法之美
登录|注册

27 | 递归树:如何借助树来求解递归算法的时间复杂度?

王争 2018-11-21
今天,我们来讲树这种数据结构的一种特殊应用,递归树。
我们都知道,递归代码的时间复杂度分析起来很麻烦。我们在第 12 节《排序(下)》那里讲过,如何利用递推公式,求解归并排序、快速排序的时间复杂度,但是,有些情况,比如快排的平均时间复杂度的分析,用递推公式的话,会涉及非常复杂的数学推导。
除了用递推公式这种比较复杂的分析方法,有没有更简单的方法呢?今天,我们就来学习另外一种方法,借助递归树来分析递归算法的时间复杂度

递归树与时间复杂度分析

我们前面讲过,递归的思想就是,将大问题分解为小问题来求解,然后再将小问题分解为小小问题。这样一层一层地分解,直到问题的数据规模被分解得足够小,不用继续递归分解为止。
如果我们把这个一层一层的分解过程画成图,它其实就是一棵树。我们给这棵树起一个名字,叫作递归树。我这里画了一棵斐波那契数列的递归树,你可以看看。节点里的数字表示数据的规模,一个节点的求解可以分解为左右子节点两个问题的求解。
通过这个例子,你对递归树的样子应该有个感性的认识了,看起来并不复杂。现在,我们就来看,如何用递归树来求解时间复杂度
归并排序算法你还记得吧?它的递归实现代码非常简洁。现在我们就借助归并排序来看看,如何用递归树,来分析递归代码的时间复杂度。
取消
完成
0/1000字
划线
笔记
复制
© 版权归极客邦科技所有,未经许可不得传播售卖。 页面已增加防盗追踪,如有侵权极客邦将依法追究其法律责任。
该试读文章来自付费专栏《数据结构与算法之美》,如需阅读全部文章,
请订阅文章所属专栏。
立即订阅
登录 后留言

精选留言(118)

  • farFlight
    假设细胞到了第三个小时是先分裂完再死亡,那么递推公式就应该是:
    f(n) = f(n-1)*2 - f(n-3)
    一次乘法和一次减法一起看作一次基本操作消耗,那么情况和斐波那契数列很像。
    最高的树应该有n层, 最短的是n/3层,每层操作数都是指数增长。
    那么时间复杂度应该是在O(2^n)量级的。
    2018-11-21
    4
    268
  • qinggeouye
    有些同学不明白点赞第一的意思,在此试着解释一下。

    假设细胞先分裂再死亡,即,每个细胞分裂三次后死亡(存活三个小时)。

    n 从第 0 个小时开始,

    n = 0,f(0) = 1

    n = 1,f(1) = 2*f(1)

    n = 2,f(2) = 2*f(1)

    n = 3,f(3) = 2*f(2) - f(0) ,减去存活了三个小时的细胞个数。

    n = 4,f(4) = 2*f(3) - f(1),减去存活了三个小时的细胞个数。

    以此类推:

    f(n) = 2*f(n-1) - f(n-3),减去存活了三个小时的细胞个数。
    2018-12-20
    11
    177
  • Jerry银银
    说个有意思的现象,我平时除了看专栏本身的内容,我也会看留言。我发现从专栏开始时,精品留言点赞数达到500多,随着专栏的前行,点赞的人越来越少了😄

    从中,也能发现端倪。

    这挺有意思的
    2018-11-27
    5
    83
  • Bryce
    点赞第一的递推可能有些问题,这里假设经过三个小时的细胞分裂后再死亡。
    通过留言可以看出有些同学可能没搞明白细胞分裂的方式,根据题意,细胞的生命周期是三个小时,一个小时后,第一个细胞分裂,此时细胞总数变成 2,但是这两个细胞的生存时间是不一样的,如果都当成新生细胞即存活时间为 0,那么给定的 3小时生命周期也就没意义了,所以这个时候其中一个细胞的生存时间变成了 1,另外一个刚分裂出来的是 0,下面简单表示一下分裂进程(-1 表示死亡)
    时间 细胞状态 (生存时间) 细胞总数
      0 0 1
      1 1 0 2
      2 2 1 0 0 4
      3 -1 2 1 1 0 0 0 0 7
      4 -1 2 2 1 1 1 1 0 0 0 0 0 0 0 13
      5 -1 -1 2 2 2 2 1 1 1 1 1 1 1
                       0 0 0 0 0 0 0 0 0 0 0 0 0 24
      .... ............................................. ....
    f0 = 1
    f1 = 2
    f2 = 4
    f3 = 7
    可以发现到第四个小时的时候,规律出来了,在第四个小时死亡的细胞是三小时前也就是第一个小时的时候同时出生的细胞,而在第一个小时同时出生的细胞数等于第一个小时前一个小时的细胞总数
    所以有递推式:f(n) = 2 * f(n - 1) - f(n - 4)
    2019-02-13
    9
    46
  • 咬尖月牙儿
    细胞分裂问题有个地方不解,1个细胞分裂之后不就变成2个新的细胞了,那么原来的细胞不就不存在了吗?那3小时后死亡怎么计算?
    2019-01-15
    2
    24
  • 菜鸡程序员
    如果先分裂,经过画图发现 是1,2,4,7,13,24,44 发现应该是f(n)=2*f(n-1)-f(n-4) 置顶是错的
    2018-12-27
    2
    21
  • 纯洁的憎恶
    思考题:
    f0=1
    f1=1+1=2
    f2=1+1+2=4
    f3=1+1+2+3-1=6 = f1 + f2
    f4=1+1+2+3-1+5-1=10 = f2+f3
    f5=1+1+2+4-1+5-1+8-2=16 = f3+f4
    f(n)= f(n-1) + f(n-2)

    与斐波那契数列的递归复杂度相同。
    2018-11-21
    1
    21
  • Laughing_Lz
    假设细胞到了第三个小时是先分裂完再死亡,递推公式为f(n) = 2f(n-1)-f(n-3)
    假设细胞到了第三个小时是先死亡再其余的分裂,递推公式为f(n) = [f(n-1)-f(n-3)]*2
    2018-12-06
    2
    18
  • 朱凯
    思路:f(n) = 2 * f(n-1) - 【n时刻点死掉的细胞数量】
    而在【n时刻点死掉的细胞数量】就是【n-3时刻点新分裂的细胞数量】;【n-3时刻点新分裂的细胞数量】就是【n-4时刻点的细胞数总数】,即f(n-4)

    故递推公式:f(n) = 2 * f(n-1) - f(n-4)
    2019-02-20
    3
    15
  • 于欣磊
    打卡,立flag的同学少了一个数量级都不止啊
    2018-11-23
    15
  • komo0104
    如果到了第三小时先分裂再死亡应该是f(n) = 2*f(n-1) - f(n-4)

    —————————-
     
     public static int func(int hour){
       if(hour == 0) return 1;
       if(hour == 1) return 2;
       if(hour == 2) return 4;
       if(hour == 3) return 7;
       return 2*func(hour -1) - func(hour - 4);
     }

    ————-
    带入hour=4
    结果: 2 * func(3)-func(0)= 13
    2018-11-22
    12
  • Brandon
    递归树分析递归算法的时间复杂度

    把递归树画出来,计算每一层和每一层的一个耗时情况,求和
    思考题:拒绝思考
    2018-12-13
    2
    8
  • 张正龙
    我是来重温算法的,所以看起来还是通俗易懂的,回想当年大学学算法一个算法最少要在poj上做几十道题才能比较好理解,算法和数据结构真不是看俩便书或者文章就能理解的,一定要是要多练习的!而且还要明白一个事实,就算练习了,过段时间你也会忘记!所以我又来重温了!
    2019-03-14
    6
  • 小罗是坏蛋
    如果第三个小时不分裂,死亡:
    f(n)=f(n-1)+f(n-2)
    第三个小时分裂之后再死亡:
    有两个公式表达
    f(n)=f(n-1)+f(n-2)+f(n-3)

    之后再用斐波那契数列中老师的树的分析方式分析,得到结果
    第三个小时不分裂,就死亡,与斐波那契数列结果相同
    第三个小时先分裂再死亡,时间复杂度在
    O(3^n/3)至O(3^n)之间
    2018-12-09
    5
  • 不成熟的萌
    假设细胞3小时候先分裂再死亡。
    life3 表示还能活3个小时, life2表示还能活2个小时,life1表示还能活1个小时
    假设在第x时刻,存活细胞数为life1 = x, life2= y, life3 = z个,总细胞sum(x)
    在第x + 1时刻,此时刻的life1细胞均来自上一时刻的life2细胞。此时刻life2细胞均来自上一时刻的life3细胞。上一时刻life1细胞死亡后,会分列均等数量life3细胞,因此上一时刻所有细胞均会分裂,所以此时刻life3细胞等于上一时刻所有细胞数。
    所以x + 1时刻,life1 = y, life2 = z, life3 = sum(x), sum(x+1) = y + z + sum(x)
    x + 2, life1 = z, life2 = sum(x), life3 = sum(x + 1), sum(x+2) = z + sum(x) + sum(x + 1)
    x + 3, life1 = sum(x), life2 = sum(x + 1), life3 = sum(x + 2) , sum(x + 3) = sum(x) + sum(x + 1) + sum(x + 2)
    因此递推式为
    sum(x) = sum(x - 1) + sum(x - 2) + sum(x - 3)
    1 sum函数
    3 sum函数
    9 sum函数
    所以是3的0次方+3的1次方+3的二次方,为几何级数,算法复杂度为O(3的n次方)
    2018-12-05
    5
  • ppingfann
    老师,有几个问题不明白:
    1. 求归并排序的时间复杂度中
    满二叉树的高度计算公式中的n指的是树中的节点的总个数,而归并排序中的n指的却是叶子节点的个数。所以归并排序中树的高度,我计算出来的是h=log2^2n-1。
    2. 实战二中
    “f(n) 分解为 f(n-1) 和 f(n-2),每次数据规模都是 -1 或者 -2,叶子节点的数据规模是 1 或者 2。“
    叶子节点为1或者2都不能再往下分叉了,所以,我计算出来的最长路径是n-2。举个具体的例子:n=5时,最长路径为3。
    我计算出来的最短路径依据n的不同还会不同,
    具体的例子:n=5时,最短路径为2,n=6时,最短路径依然为2。

    是我理解的有偏差吗?请老师指点。
    2018-11-21
    5
  • Geek_zy
    课后题目得时间复杂度为 2^(N+1)
    树得最后三层减去树得前边的层数。即为时间复杂度。。
    2018-12-19
    4
  • 沉睡的木木夕
    有几点问题不懂
    1.实战二:分析斐波那契数列的时间复杂度 一节提到
    “f(n) 分解为 f(n-1) 和 f(n-2),每次数据规模都是 -1 或者 -2,叶子节点的数据规模是 1 或者 2。所以,从根节点走到叶子节点,每条路径是长短不一的。如果每次都是 -1,那最长路径大约就是 n;如果每次都是 -2,那最短路径大约就是 n/2。”数据规模都是-1,-2 这怎么理解?每次都是-1,最长路径大约就是n 这又是怎么理解的?
    2.实战3中提到
    “第一层分解有 n 次交换操作,第二层有 n 个节点,每个节点分解需要 n-1 次交换,所以第二层总的交换次数是 n*(n-1)。第三层有 n*(n-1) 个节点,每个节点分解需要 n-2 次交换,所以第三层总的交换次数是 n*(n-1)*(n-2)。”
    交换操作的次数是怎么的出来的?
    这对于我来讲就好比,数学老师讲了一堆看似简单的东西(有同学基础不好),最后老师最后落笔:所以1+1=2,但我还是一脸懵逼
    2018-11-21
    1
    4
  • 小林子
    f(0) = 1
    f(1) = 2
    f(2) = 4
    f(3) = 8
    f(n) = f(n-1) + f(n-2) + f(n-3) + f(n-4)
    2018-11-21
    3
  • Reco
    f(n) = 2f(n - 1) - f(n - 4)
    2019-07-11
    2
收起评论
99+
返回
顶部