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

Nov 21, 2018

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



下载APP





关闭

讲堂部落提薪训练营云原生训练营架构实战营企业版极客商城兑换中心 App下载浏览器插件

渠道合作

推荐作者

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

2018-11-21 王争来自北京

《数据结构与算法之美》

课程介绍



讲述：冯永吉

时长13:06大小11.96M



今天，我们来讲这种数据结构的一种特殊应用，递归树。
我们都知道，递归代码的时间复杂度分析起来很麻烦。我们在第 12 节《排序（下）》那里讲过，如何利用递推公式，求解归并排序、快速排序的时间复杂度，但是，有些情况，比如快排的平均时间复杂度的分析，用递推公式的话，会涉及非常复杂的数学推导。
除了用递推公式这种比较复杂的分析方法，有没有更简单的方法呢？今天，我们就来学习另外一种方法，借助递归树来分析递归算法的时间复杂度。
递归树与时间复杂度分析我们前面讲过，递归的思想就是，将大问题分解为小问题来求解，然后再将小问题分解为小小问题。这样一层一层地分解，直到问题的数据规模被分解得足够小，不用继续递归分解为止。
如果我们把这个一层一层的分解过程画成图，它其实就是一棵树。我们给这棵树起一个名字，叫作递归树。我这里画了一棵斐波那契数列的递归树，你可以看看。节点里的数字表示数据的规模，一个节点的求解可以分解为左右子节点两个问题的求解。
通过这个例子，你对递归树的样子应该有个感性的认识了，看起来并不复杂。现在，我们就来看，如何用递归树来求解时间复杂度。
归并排序算法你还记得吧？它的递归实现代码非常简洁。现在我们就借助归并排序来看看，如何用递归树，来分析递归代码的时间复杂度。
归并排序的原理我就不详细介绍了，如果你忘记了，可以回看一下第 12 节的内容。归并排序每次会将数据规模一分为二。我们把归并排序画成递归树，就是下面这个样子：
因为每次分解都是一分为二，所以代价很低，我们把时间上的消耗记作常量 1。归并算法中比较耗时的是归并操作，也就是把两个子数组合并为大数组。从图中我们可以看出，每一层归并操作消耗的时间总和是一样的，跟要排序的数据规模有关。我们把每一层归并操作消耗的时间记作 n。
现在，我们只需要知道这棵树的高度 h，用高度 h 乘以每一层的时间消耗 n，就可以得到总的时间复杂度 O(n∗h)。
从归并排序的原理和递归树，可以看出来，归并排序递归树是一棵满二叉树。我们前两节中讲到，满二叉树的高度大约是 log2​n，所以，归并排序递归实现的时间复杂度就是 O(nlogn)。我这里的时间复杂度都是估算的，对树的高度的计算也没有那么精确，但是这并不影响复杂度的计算结果。
利用递归树的时间复杂度分析方法并不难理解，关键还是在实战，所以，接下来我会通过三个实际的递归算法，带你实战一下递归的复杂度分析。学完这节课之后，你应该能真正掌握递归代码的复杂度分析。
实战一：分析快速排序的时间复杂度在用递归树推导之前，我们先来回忆一下用递推公式的分析方法。你可以回想一下，当时，我们为什么说用递推公式来求解平均时间复杂度非常复杂？
快速排序在最好情况下，每次分区都能一分为二，这个时候用递推公式 T(n)=2T(2n​)+n，很容易就能推导出时间复杂度是 O(nlogn)。但是，我们并不可能每次分区都这么幸运，正好一分为二。
我们假设平均情况下，每次分区之后，两个分区的大小比例为 1:k。当 k=9 时，如果用递推公式的方法来求解时间复杂度的话，递推公式就写成 T(n)=T(10n​)+T(109n​)+n。
这个公式可以推导出时间复杂度，但是推导过程非常复杂。那我们来看看，用递归树来分析快速排序的平均情况时间复杂度，是不是比较简单呢？
我们还是取 k 等于 9，也就是说，每次分区都很不平均，一个分区是另一个分区的 9 倍。如果我们把递归分解的过程画成递归树，就是下面这个样子：
快速排序的过程中，每次分区都要遍历待分区区间的所有数据，所以，每一层分区操作所遍历的数据的个数之和就是 n。我们现在只要求出递归树的高度 h，这个快排过程遍历的数据个数就是 h∗n ，也就是说，时间复杂度就是 O(h∗n)。
因为每次分区并不是均匀地一分为二，所以递归树并不是满二叉树。这样一个递归树的高度是多少呢？
我们知道，快速排序结束的条件就是待排序的小区间，大小为 1，也就是说叶子节点里的数据规模是 1。从根节点 n 到叶子节点 1，递归树中最短的一个路径每次都乘以 101​，最长的一个路径每次都乘以 109​。通过计算，我们可以得到，从根节点到叶子节点的最短路径是 log10​n，最长的路径是 log910​​n。
所以，遍历数据的个数总和就介于 nlog10​n 和 nlog910​​n 之间。根据复杂度的大 O 表示法，对数复杂度的底数不管是多少，我们统一写成 logn，所以，当分区大小比例是 1:9 时，快速排序的时间复杂度仍然是 O(nlogn)。
刚刚我们假设 k=9，那如果 k=99，也就是说，每次分区极其不平均，两个区间大小是 1:99，这个时候的时间复杂度是多少呢？
我们可以类比上面 k=9 的分析过程。当 k=99 的时候，树的最短路径就是 log100​n，最长路径是 log99100​​n，所以总遍历数据个数介于 nlog100​n 和 nlog99100​​n 之间。尽管底数变了，但是时间复杂度也仍然是 O(nlogn)。
也就是说，对于 k 等于 9，99，甚至是 999，9999……，只要 k 的值不随 n 变化，是一个事先确定的常量，那快排的时间复杂度就是 O(nlogn)。所以，从概率论的角度来说，快排的平均时间复杂度就是 O(nlogn)。
实战二：分析斐波那契数列的时间复杂度在递归那一节中，我们举了一个跨台阶的例子，你还记得吗？那个例子实际上就是一个斐波那契数列。为了方便你回忆，我把它的代码实现贴在这里。
int f(int n) {
  if (n == 1) return 1;
  if (n == 2) return 2;
  return f(n-1) + f(n-2);
}
这样一段代码的时间复杂度是多少呢？你可以先试着分析一下，然后再来看，我是怎么利用递归树来分析的。
我们先把上面的递归代码画成递归树，就是下面这个样子：
这棵递归树的高度是多少呢？
f(n) 分解为 f(n−1) 和 f(n−2)，每次数据规模都是 −1 或者 −2，叶子节点的数据规模是 1 或者 2。所以，从根节点走到叶子节点，每条路径是长短不一的。如果每次都是 −1，那最长路径大约就是 n；如果每次都是 −2，那最短路径大约就是 2n​。
每次分解之后的合并操作只需要一次加法运算，我们把这次加法运算的时间消耗记作 1。所以，从上往下，第一层的总时间消耗是 1，第二层的总时间消耗是 2，第三层的总时间消耗就是 22。依次类推，第 k 层的时间消耗就是 2k−1，那整个算法的总的时间消耗就是每一层时间消耗之和。
如果路径长度都为 n，那这个总和就是 2n−1。
如果路径长度都是 2n​ ，那整个算法的总的时间消耗就是 22n​−1。
所以，这个算法的时间复杂度就介于 O(2n) 和 O(22n​) 之间。虽然这样得到的结果还不够精确，只是一个范围，但是我们也基本上知道了上面算法的时间复杂度是指数级的，非常高。
实战三：分析全排列的时间复杂度前面两个复杂度分析都比较简单，我们再来看个稍微复杂的。
我们在高中的时候都学过排列组合。“如何把 n 个数据的所有排列都找出来”，这就是全排列的问题。
我来举个例子。比如，1，2，3 这样 3 个数据，有下面这几种不同的排列：
1, 2, 3
1, 3, 2
2, 1, 3
2, 3, 1
3, 1, 2
3, 2, 1
如何编程打印一组数据的所有排列呢？这里就可以用递归来实现。
如果我们确定了最后一位数据，那就变成了求解剩下 n−1 个数据的排列问题。而最后一位数据可以是 n 个数据中的任意一个，因此它的取值就有 n 种情况。所以，“n 个数据的排列”问题，就可以分解成 n 个“n−1 个数据的排列”的子问题。
如果我们把它写成递推公式，就是下面这个样子：
假设数组中存储的是1，2， 3...n。
        
f(1,2,...n) = {最后一位是1, f(n-1)} + {最后一位是2, f(n-1)} +...+{最后一位是n, f(n-1)}。
如果我们把递推公式改写成代码，就是下面这个样子：
// 调用方式：
// int[]a = a={1, 2, 3, 4}; printPermutations(a, 4, 4);
// k表示要处理的子数组的数据个数
public void printPermutations(int[] data, int n, int k) {
  if (k == 1) {
    for (int i = 0; i < n; ++i) {
      System.out.print(data[i] + " ");
    }
    System.out.println();
  }
  for (int i = 0; i < k; ++i) {
    int tmp = data[i];
    data[i] = data[k-1];
    data[k-1] = tmp;
    printPermutations(data, n, k - 1);
    tmp = data[i];
    data[i] = data[k-1];
    data[k-1] = tmp;
  }
}
如果不用我前面讲的递归树分析方法，这个递归代码的时间复杂度会比较难分析。现在，我们来看下，如何借助递归树，轻松分析出这个代码的时间复杂度。
首先，我们还是画出递归树。不过，现在的递归树已经不是标准的二叉树了。
第一层分解有 n 次交换操作，第二层有 n 个节点，每个节点分解需要 n−1 次交换，所以第二层总的交换次数是 n∗(n−1)。第三层有 n∗(n−1) 个节点，每个节点分解需要 n−2 次交换，所以第三层总的交换次数是 n∗(n−1)∗(n−2)。
以此类推，第 k 层总的交换次数就是 n∗(n−1)∗(n−2)∗...∗(n−k+1)。最后一层的交换次数就是 n∗(n−1)∗(n−2)∗...∗2∗1。每一层的交换次数之和就是总的交换次数。
n + n*(n-1) + n*(n-1)*(n-2) +... + n*(n-1)*(n-2)*...*2*1
这个公式的求和比较复杂，我们看最后一个数，n∗(n−1)∗(n−2)∗...∗2∗1 等于 n!，而前面的 n−1 个数都小于最后一个数，所以，总和肯定小于 n∗n!，也就是说，全排列的递归算法的时间复杂度大于 O(n!)，小于 O(n∗n!)，虽然我们没法知道非常精确的时间复杂度，但是这样一个范围已经让我们知道，全排列的时间复杂度是非常高的。
这里我稍微说下，掌握分析的方法很重要，思路是重点，不要纠结于精确的时间复杂度到底是多少。
内容小结今天，我们用递归树分析了递归代码的时间复杂度。加上我们在排序那一节讲到的递推公式的时间复杂度分析方法，我们现在已经学习了两种递归代码的时间复杂度分析方法了。
有些代码比较适合用递推公式来分析，比如归并排序的时间复杂度、快速排序的最好情况时间复杂度；有些比较适合采用递归树来分析，比如快速排序的平均时间复杂度。而有些可能两个都不怎么适合使用，比如二叉树的递归前中后序遍历。
时间复杂度分析的理论知识并不多，也不复杂，掌握起来也不难，但是，在我们平时的工作、学习中，面对的代码千差万别，能够灵活应用学到的复杂度分析方法，来分析现有的代码，并不是件简单的事情，所以，你平时要多实战、多分析，只有这样，面对任何代码的时间复杂度分析，你才能做到游刃有余、毫不畏惧。
课后思考1 个细胞的生命周期是 3 小时，1 小时分裂一次。求 n 小时后，容器内有多少细胞？请你用已经学过的递归时间复杂度的分析方法，分析一下这个递归问题的时间复杂度。
欢迎留言和我分享，我会第一时间给你反馈。

分享给需要的人，Ta购买本课程，你将得20元

生成海报并分享

赞 98

提建议

26 | 红黑树（下）：掌握这些技巧，你也可以实现一个红黑树

28 | 堆和堆排序：为什么说堆排序没有快速排序快？

 写留言

精选留言(218)

farFlight
2018-11-21
假设细胞到了第三个小时是先分裂完再死亡，那么递推公式就应该是： f(n) = f(n-1)*2 - f(n-3) 一次乘法和一次减法一起看作一次基本操作消耗，那么情况和斐波那契数列很像。最高的树应该有n层，最短的是n/3层，每层操作数都是指数增长。那么时间复杂度应该是在O(2^n)量级的。
共 29 条评论
478
qinggeouye
2018-12-20
有些同学不明白点赞第一的意思，在此试着解释一下。假设细胞先分裂再死亡，即，每个细胞分裂三次后死亡（存活三个小时）。 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)，减去存活了三个小时的细胞个数。
展开
共 24 条评论
432
Bryce
2019-02-13
点赞第一的递推可能有些问题，这里假设经过三个小时的细胞分裂后再死亡。通过留言可以看出有些同学可能没搞明白细胞分裂的方式，根据题意，细胞的生命周期是三个小时，一个小时后，第一个细胞分裂，此时细胞总数变成 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)
展开
共 18 条评论
174
Jerry银银
2018-11-27
说个有意思的现象，我平时除了看专栏本身的内容，我也会看留言。我发现从专栏开始时，精品留言点赞数达到500多，随着专栏的前行，点赞的人越来越少了😄 从中，也能发现端倪。这挺有意思的
展开
共 27 条评论
159
朱凯
2019-02-20
思路：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)
共 7 条评论
94
ɴɪᴋᴇʀ
2020-07-08
***************************************************************************************** 我看了一些评论，感觉都不太对，也看到了正确的答案，但是并没有讲清楚。所以来总结一下，让大家一起明白。最开始为0的时刻，放入了1个细胞，然后1小时的时候，分裂变为了2个细胞，然后2小时的时候，分裂成了4个细胞，然后3小时的时候，分裂成了8个细胞，但是最早的那1个细胞死掉了，所以最终剩下7个细胞。列举时刻与个数的关系: 时刻: 0 1 2 3 个数: 1 2 4 7 将细胞分裂分为两个步骤，先分裂，后死亡。比如第四个小时的时候，从3小时的7个细胞分裂成14个，然后计算要死亡细胞的个数，直观上我们会认为，第1小时的时候2个细胞现在应该会死亡了，所以4小时的时候，细胞个数应该是7*2 - 2 = 12个，得到4小时之后的公式f(n) = f(n-1) * 2 - f(n-3)。但这是错误的，因为第1小时的2个细胞，其中一个已经在第3小时的时候死掉了，因此第4小时的时候只会死掉1个细胞，正确的个数应该是 14 - 1 = 13. 经过这样分析，死掉的细胞数并不是前3小时的细胞总数f(n-3)，因为这里面包含n-3时刻新生的细胞和老细胞，很显然老细胞在n时刻之前就已经死完了。此时死掉的细胞数应该是n-3时刻新生的细胞数，而n-3时刻新生的细胞数正是前一时刻老细胞分裂而来的即f(n-4)，因此正确的计算公式是 f(n) = f(n-1) * 2 - f(n-4)。用递归代码写出来就是 int F(int n){ If(n<0) return 0; If(n==0) return 1; If(n==1) return 2; If(n==2) return 4; If(n==3) return 7; return F(n-1) * 2 - F(n-4); } 不知道你们看懂了没有，不过我是看懂了，这确实是正确答案。 ***************************************************************************************
展开
共 6 条评论
91
纯洁的憎恶
2018-11-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）与斐波那契数列的递归复杂度相同。
展开
共 7 条评论
42
菜鸡程序员
2018-12-27
如果先分裂，经过画图发现是1，2，4，7，13，24，44 发现应该是f(n)=2*f(n-1)-f(n-4) 置顶是错的
共 2 条评论
34
张正龙
2019-03-14
我是来重温算法的，所以看起来还是通俗易懂的，回想当年大学学算法一个算法最少要在poj上做几十道题才能比较好理解，算法和数据结构真不是看俩便书或者文章就能理解的，一定要是要多练习的！而且还要明白一个事实，就算练习了，过段时间你也会忘记！所以我又来重温了！
共 4 条评论
32
咬尖月牙儿
2019-01-15
细胞分裂问题有个地方不解，1个细胞分裂之后不就变成2个新的细胞了，那么原来的细胞不就不存在了吗？那3小时后死亡怎么计算？
共 9 条评论
32
分清云淡
2018-11-23
打卡，立flag的同学少了一个数量级都不止啊
22
Laughing_Lz
2018-12-06
假设细胞到了第三个小时是先分裂完再死亡，递推公式为f(n) = 2f(n-1)-f(n-3) 假设细胞到了第三个小时是先死亡再其余的分裂，递推公式为f(n) = [f(n-1)-f(n-3)]*2
共 2 条评论
20
komo0104
2018-11-22
如果到了第三小时先分裂再死亡应该是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
展开
15
色即是空
2018-12-13
递归树分析递归算法的时间复杂度把递归树画出来，计算每一层和每一层的一个耗时情况，求和思考题：拒绝思考
共 4 条评论
14
小罗是坏蛋
2018-12-09
如果第三个小时不分裂，死亡： 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)之间
展开
11
其
2019-06-18
说下递推公式吧，2*f(n-1)是肯定的，问题只出在后面的减数上，个人理解减数应该是第n-3次新生的细胞数，也就是第n-3次相比于第n-4次的增量，也就是f(n-3)-f(n-4)。总结一下，递推公式应该为： f(n) = f(n-1)*2 - (f(n-3)-f(n-4)) f(n) = f(n-1)*2 - f(n-3) + f(n-4) 初始条件为f(-1) = 0，f(0) = 1
展开
共 1 条评论
9
Jeff
2020-09-24
这个问题如果改一下，争议就会小了。假设有一种动物，只能存活 3 个小时，开始时只有 1 只，每隔 1 小时可以生产一只新的。求 n 小时后，共有多少只该动物存活。假设先生完，再死。开始，第 0 小时， f(0) = 1; 第 1 小时，仅 1 只，可生产 1 只，在原基础上 + 1，没有死亡，f(1) = 2; 第 2 小时，有两只，可再生产 2 只，没有死亡，f(2) = 4; 第 3 小时，有 4 只，可在生产 4 只，死亡 1 只（第 0 小时那只死了），f(3)=7; 第 4 小时，有7只，可在生产 7 只，死亡 1 只（第 1 小时新增的那只死了）， f(4) = 13; 第 5 小时，有 13 只，可再生产 13 只，死亡个数为第 2 小时时新增的个数（即 f（k-3）- f(k-4)), f(5) = 24. 第 k 层的个数，在第 k-1 层个数基础上，新增 k-1，死亡 k-3 层新增的个数（即 f(k-3) - f(k-4))。 f(k) = 2 f(k-1) - [f(k-3) - f(k-4)] (k>=4). 时间复杂度是和斐波那契数列一样， O(2^n) 级别。
展开
共 2 条评论
8
沉睡的木木夕
2018-11-21
有几点问题不懂 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，但我还是一脸懵逼
展开
共 4 条评论
7
If_
2019-11-01
我就是那种原来都不甚清楚，很大部分都不了解，前边专栏看了四五六七遍的，刚刚来这的那种同学。走那么快干嘛，走稳点不好吗？
6
不成熟的萌
2018-12-05
假设细胞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次方)
展开
6

新人学习立返 50% 购课币

去订阅《数据结构与算法之美》新人首单¥68

