27 | 递归树：如何借助树来求解递归算法的时间复杂度？
王争
该思维导图由 AI 生成，仅供参考
今天，我们来讲这种数据结构的一种特殊应用，递归树。
我们都知道，递归代码的时间复杂度分析起来很麻烦。我们在第 12 节《排序（下）》那里讲过，如何利用递推公式，求解归并排序、快速排序的时间复杂度，但是，有些情况，比如快排的平均时间复杂度的分析，用递推公式的话，会涉及非常复杂的数学推导。
除了用递推公式这种比较复杂的分析方法，有没有更简单的方法呢？今天，我们就来学习另外一种方法，借助递归树来分析递归算法的时间复杂度。
递归树与时间复杂度分析
我们前面讲过，递归的思想就是，将大问题分解为小问题来求解，然后再将小问题分解为小小问题。这样一层一层地分解，直到问题的数据规模被分解得足够小，不用继续递归分解为止。
如果我们把这个一层一层的分解过程画成图，它其实就是一棵树。我们给这棵树起一个名字，叫作递归树。我这里画了一棵斐波那契数列的递归树，你可以看看。节点里的数字表示数据的规模，一个节点的求解可以分解为左右子节点两个问题的求解。
通过这个例子，你对递归树的样子应该有个感性的认识了，看起来并不复杂。现在，我们就来看，如何用递归树来求解时间复杂度。
归并排序算法你还记得吧？它的递归实现代码非常简洁。现在我们就借助归并排序来看看，如何用递归树，来分析递归代码的时间复杂度。
公开
同步至部落
取消
完成
0/2000
荧光笔
直线
曲线笔记
复制
AI
- 深入了解
- 翻译
- 解释
- 总结
递归树分析方法是一种用于分析递归算法时间复杂度的有效工具。通过将递归过程可视化成树状结构，可以更直观地理解递归算法的时间消耗。本文以归并排序和快速排序为例，详细介绍了如何利用递归树来分析递归算法的时间复杂度。通过递归树的高度和每层的时间消耗，可以得到总的时间复杂度。对于快速排序，即使在最坏情况下分区极不平均，时间复杂度仍然保持在O(nlogn)。此外，文章还通过实例详细阐述了递归树的应用，对读者进行了深入的技术讲解，有助于读者快速掌握递归代码的复杂度分析。除此之外，文章还介绍了递归树分析方法在斐波那契数列和全排列问题中的应用，展示了该方法的广泛适用性。通过本文的学习，读者可以掌握两种递归代码的时间复杂度分析方法，为分析各种代码的时间复杂度提供了有力工具。文章最后提出了一个课后思考问题，引发读者思考和讨论。整体而言，本文深入浅出地介绍了递归树分析方法，对读者理解递归算法的复杂度分析具有重要指导意义。
仅可试看部分内容，如需阅读全部内容，请付费购买文章所属专栏
《数据结构与算法之美》，新⼈⾸单¥68
《数据结构与算法之美》，新⼈⾸单¥68
立即购买
© 版权归极客邦科技所有，未经许可不得传播售卖。 页面已增加防盗追踪，如有侵权极客邦将依法追究其法律责任。
登录 后留言
全部留言(221)
- 最新
- 精选
月迷津渡第三个例子的排列组合代码相当晦涩啊，我跟了好几遍还是没能完全理解。作者回复: 那就先放一放，抽空再看吧
2019-08-0726
旅途实战三中 为什么最后的复杂度是所有层加起来？第一层推导为第二层,逐渐推导为最后一层,所以复杂度应该是最后一层啊？作者回复: 每次分解操作（比如：f(n)分解为n个f(n-1)来计算的时候）都有成本的，要把每次分解操作的成本都累加起来。
2019-06-222
Rise看完后，对时间复杂度有了很大的疑惑，为什么树的遍历时间复杂度是O(n)，树的遍历也是用的递归，既然公式和递归树都不适合，该怎么推导，既然都是递归，为什么公式和递归树都不适合推导树的遍历？作者回复: 你这不是抬杠吗：）不适合的意思不是绝对绝对绝对不可以。就是分析起来比较麻烦。换个思路分析不好吗？
2019-01-241
Joiner老师，对于两种递归代码的时间复杂度分析方法都不适用的递归代码，还有其他的方法吗？作者回复: 那得具体问题具体分析了
2019-10-12
junjun我没明白一个细胞分裂为两个之后，自身还存在不，如果不存在，那怎么会死亡呢？只有不存在的时候，才是f（n） = 2 * f（n-1） - f（n-3）作者回复: 存在的，到期才死亡的
2019-09-23
神佑小鹿到底哪个是正确的方法？？作者回复: 你是指的哪个问题呢？
2019-08-22
建强思考题：根据题意，初始细胞数1个，1小时后分裂为2个，2小时后，2个细胞分裂为4个，3小时后，最早的那个细胞死亡，剩下的三个细胞各自分裂出一个细胞，总数为6个，自3小时后， 每经过一小时，都会有一个细胞死亡，因此，递归表达式：f(n) = (f(n-1)-1) * 2，递归终止条件：f(3) = 6，根据递归表达式画出递归树： 递归树： f(n) | | (f(n-1)-1) * 2 | | (f(n-2)-1) * 2 | | .... | | f(3) = 6 树的高度为：h = n-3，每一层的运算次数只有一次，因此时间复杂度O(h) = O(n-3) = O(n) 以上理解不知是否正确，请老师指正。作者回复: 参考斐波那契数列的那个推导
2019-08-03- Geek_18b741关于斐波那契数列的复杂度问题，我有疑问。文章说每层计算量是2^(k-1)，是逐渐增加的，可是我画了一个f(6)的树，计算量分别是1、2、2、1。一开始确实是增加的，但是到了后面，因为有些路径很早就结束了，所以不是越来越多呀。
作者回复: 你说都没错，并不是一颗很规则的树，是一个斜着的歪歪的树，所以我们在分析复杂度的时候，提到了最短路径、最长路径。
2019-07-01 
Tom第三个案例的递归代码看了几遍没看懂，老师能否再详细分解描述一下作者回复: 排列组合的，你可以网上搜下如何写。
2019-05-26
好雨当春既然原递归问题等价于子递归问题，那就应该直接跳到最后的叶子递归问题求时间复杂度就好了吧，叶子结点以前的时间应该不再计算了吧？作者回复: 没有太看懂你说的呢
2019-03-24
收起评论
