首先，该文章来自于极客时间网站，王争的专栏——《数据结构与算法之美》，我这里只是做简单的解释、记录并添加自己的见解，只是作为个人笔记，若侵权，马上删除。最后建议直接去该网站上购买该课程看原作者的讲解，一来是支持作者，二来是作者写的确实不错。
之前我们使用过递推公式求解归并排序、快速排序的时间复杂度。但是有些情况，比如说使用递推公式求解快排的平均时间复杂度，会涉及到非常复杂的数学推导。此时使用递归树来分析递归算法的时间复杂度会更加简单。
递归树与时间复杂度分析
递归的思想就是：将大问题分解为小问题来求解，然后再将小问题分解为小小问题。这样一层一层地分解，直到问题的数据规模被分解得足够小，不用继续递归分解为止。
如果把这个一层一层的分解过程画成图，它其实就是递归树。如下为斐波那契数列的递归树，节点里的数字表示数据的规模，一个节点的求解可以分解为左右子节点两个问题的求解。
那么如何使用递归树来求解时间复杂度呢？我们以归并算法为例进行分析。归并排序每次都会将数据规模一分为二。画成递归树如下：
每次分解都是一分为二，代价很低，记时间上的消耗为常量1。归并算法中比较耗时的是归并操作，也就是把两个子数组合并为大数组。从图中可以看出，每一行归并操作消耗的时间总和是一样的，跟要排序的数据规模有关。我们把每一层归并操作消耗的时间记作 $n$。
现在，我们只需要知道这颗树的高度$h$，用高度$h$乘以每一层的时间消耗$n$得到总的时间复杂度为$O(n\times h)$。
而从归并排序的原理和递归树得知，归并排序是一颗满二叉树，其高度大约为$O(log_2n)$，所以归并排序递归实现的时间复杂度就是 $O(nlogn)$。
实战一：分析快速排序的时间复杂度
快速排序在最好的情况下，每次分区都能一分为二，此时递推公式为$T(n)=2T(\frac{n}{2})+n$，很容易推导出来时间复杂度为$O(nlogn)$。但是，并不可能每次分区都这么幸运，正好一分为二。
假设平均情况下，每次分区后两个分区的大小比例为$1 : k$。当$k=9$时，如果用递推公式求解时间复杂度，递推公式可以写作$T(n)=T(\frac{n}{10})+T(\frac{9n}{10})+n$。此时用这个公式推导时间复杂度特别复杂，现在我们尝试借助递归树来分析平均情况时间复杂度。
我们还是取$k=9$，也就是每次分区很不平均时。我们把递归分解过程画成递归树。如下所示：
快速排序过程中，每次分区都要遍历带分区区间的所有数据，所以每一层分区操作所遍历的数据的个数之和就是 $n$。我们现在只要求出递归树的高度 $h$，这个快排过程遍历的数据个数就是 $h∗n$ ，也就是说，时间复杂度就是 $O(h∗n)$。
但是每次分区并不是均匀地一分为二，所以递归树并不是满二叉树。那这样的递归树高度是多少呢？
快速排序结束的条件是待排序的小区间，大小为 1，也就是叶子节点里的数据规模是 1。从根节点$n$到叶子节点 1，递归树中最短的一个路径每次都乘以$\frac{1}{10}$，最长的一个路径每次都乘以$\frac{9}{10}$。所以，从根节点到叶子节点的最短路径为$log_{10}n$，最长的路径为$log_{\frac{10}{9}}n$。
所以遍历数据的个数总和介于$nlog_{10}n$和$nlog_{\frac{10}{9}}n$之间。按照复杂度的大O表示法，不管复杂度的底数为多少，统一写成$logn$。所以，当分区大小比例是 1:9 时，快速排序的时间复杂度仍然是 $O(nlogn)$。
那么更极端一点，当$k=99$时，树的最短路径就是 $log_{100}n$，最长路径是$log_{\frac{100}{99}}n$，所以总遍历数据个数介于$nlog_{100}n$和$nlog_{\frac{100}{99}}n$之间。尽管底数变了，但是时间复杂度也仍然是 $O(nlogn)$。
也就是说，对于 $k$ 等于 9，99，甚至是 999，9999……，只要 $k$ 的值不随 $n$ 变化，是一个事先确定的常量，那快排的时间复杂度就是 $O(nlogn)$。所以，从概率论的角度来说，快排的平均时间复杂度就是 $O(nlogn)$。
实战二：分析斐波那契数列的时间复杂度
斐波那契数列的代码如下：
1 | int f(int n) { |
我们先把上面的递归代码画成递归树，如下所示：
$f(n)$分解为$f(n-1)$和$f(n-2)$，每次数据规模都是-1或者-2，叶子节点的数据规模是 1 或者 2。所以，从根节点走到叶子节点，每条路径是长短不一的。如果每次都是 −1，那最长路径大约就是 $n$；如果每次都是 −2，那最短路径大约就是$\frac{n}{2}$。
每次分解之后的合并操作只需要一次加法运算，我们把这次加法运算的时间消耗记作 1。所以，从上往下，第一层的总时间消耗是 1，第二层的总时间消耗是 2，第三层的总时间消耗就是 $2^2$。依次类推，第 k 层的时间消耗就是 $2^{k−1}$，那整个算法的总的时间消耗就是每一层时间消耗之和。
如果路径长度都为 $n$，那这个总和就是 $2^n−1$。
如果路径长度都是$\frac{n}{2}$，那整个算法的总的时间消耗就是$2^{\frac{n}{2}}−1$。
所以这个算法的时间复杂度介于$O(2^n)$和$O(2^{\frac{n}{2}})$之间。虽然这样得到的结果还不够精确，只是一个范围，但是我们也基本上知道了上面算法的时间复杂度是指数级的，非常高。
实战三：分析全排列的时间复杂度
全排列问题的定义为：如何把 $n$个数据的所有排列都找出来。比如1，2，3这样三个数据有下面这几种不同的排列：
1 | 1, 2, 3 |
可以使用递归的方法编程打印一组数据的所有排列。具体而言，如果我们确定了最后一位数据，那就变成了求解剩下 $n−1$ 个数据的排列问题。而最后一位数据可以是 $n$ 个数据中的任意一个，因此它的取值就有 $n$ 种情况。所以，“$n$ 个数据的排列”问题，就可以分解成 $n$ 个“$n−1$ 个数据的排列”的子问题。
如果写成递推公式，就是下面这个样子：
1 | 假设数组中存储的是1，2， 3...n。 |
代码如下：
1 | // 调用方式： |
借助递归树可以轻松分析出这个代码的时间复杂度。首先我们还是画出递归树，不过现在的递归树已经不是标准的二叉树了。
第一层分解有 $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$。每一层的交换次数之和就是总的交换次数。
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 小时后，容器内有多少细胞？请你用已经学过的递归时间复杂度的分析方法，分析一下这个递归问题的时间复杂度。
答：假设细胞到第三个小时先分裂后死亡，那么递归公式为$f(n)=f(n-1)*2-f(n-4)$。值得注意的是，这里之所以减去$f(n-4)$而不是$f(n-3)$，是因为死掉的细胞数应该是$n-3$时刻新生的细胞数，而n-3时刻新生的细胞数正是前一时刻分裂而来的即$f(n-4)$。一次乘法和一次减法一起看作一次基本操作消耗，那么情况和斐波那契数列很像。时间复杂度在$O(3^n/3）$至$O(3^n)$之间？？？
