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

精选留言(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