[toc]
递归树与时间复杂度分析
递归代码的时间复杂度分析起来很麻烦，除了用递推公式这种比较复杂的分析方法，还可以借助递归树来分析递归算法的时间复杂度。
递归的思想就是，将大问题分解为小问题来求解，然后再将小问题分解为小小问题。这样一层一层地分解，直到问题的数据规模被分解得足够小，不用继续递归分解为止。
如果我们把这个一层一层的分解过程画成图，它其实就是一棵树。我们给这棵树起一个名字，叫作递归树。节点里的数字表示数据的规模，一个节点的求解可以分解为左右子节点两个问题的求解。
把归并排序画成递归树，就是下面这个样子：
因为每次分解都是一分为二，所以代价很低，我们把时间上的消耗记作常量 1。归并算法中比较耗时的是归并操作，也就是把两个子数组合并为大数组。从图中我们可以看出，每一层归并操作消耗的时间总和是一样的，跟要排序的数据规模有关。我们把每一层归并操作消耗的时间记作 n。
现在，我们只需要知道这棵树的高度 h，用高度 h 乘以每一层的时间消耗 n，就可以得到总的时间复杂度 O(n*h)。
从归并排序的原理和递归树，可以看出来，归并排序递归树是一棵满二叉树。我们前两节中讲到，满二叉树的高度大约是 log~2~n，所以，归并排序递归实现的时间复杂度就是 O(nlogn)。这里的时间复杂度都是估算的，对树的高度的计算也没有那么精确，但是这并不影响复杂度的计算结果。
实战一：分析快速排序的时间复杂度
快速排序在最好情况下，每次分区都能一分为二，这个时候用递推公式 ，很容易就能推导出时间复杂度是 O(nlogn)。但是，我们并不可能每次分区都这么幸运，正好一分为二。
假设平均情况下，每次分区之后，两个分区的大小比例为 1:k。当 k=9 时，如果用递推公式的方法来求解时间复杂度的话，递推公式就写成。
快速排序的过程中，每次分区都要遍历待分区区间的所有数据，所以，每一层分区操作所遍历的数据的个数之和就是 n。我们现在只要求出递归树的高度 h，这个快排过程遍历的数据个数就是 h∗n ，也就是说，时间复杂度就是 O(h∗n)。
快速排序结束的条件就是待排序的小区间，大小为 1，也就是说叶子节点里的数据规模是 1。从根节点 n 到叶子节点 1，递归树中最短的一个路径每次都乘以 1/10，最长的一个路径每次都乘以 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，9999，甚至是 999999，99999999……，只要 k 的值不随 n 变化，是一个事先确定的常量，那快排的时间复杂度就是 O(nlogn)。所以，从概率论的角度来说，快排的平均时间复杂度就是 O(nlogn)。
实战二：分析斐波那契数列的时间复杂度
从根节点走到叶子节点，每条路径是长短不一的。如果每次都是 −1，那最长路径大约就是 n；如果每次都是 −2，那最短路径大约就是 n/2。
每次分解之后的合并操作只需要一次加法运算，我们把这次加法运算的时间消耗记作 1。所以，从上往下，第一层的总时间消耗是 1，第二层的总时间消耗是 2，第三层的总时间消耗就是 2^2^。依次类推，第 k 层的时间消耗就是 2^k−1^，那整个算法的总的时间消耗就是每一层时间消耗之和。
如果路径长度都为 n，那这个总和就是 2^n^−1。
如果路径长度都是 n/2 ，那整个算法的总的时间消耗就是 2^n/2^−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−1 个数据的排列问题。而最后一位数据可以是 n 个数据中的任意一个，因此它的取值就有 nn种情况。所以，“n 个数据的排列”问题，就可以分解成 n 个“n−1 个数据的排列”的子问题。
第一层分解有 nn次交换操作，第二层有 n 个节点，每个节点分解需要 n−1 次交换，所以第二层总的交换次数是 n∗(n−1)。第三层有 n∗(n−1)n∗(n−1) 个节点，每个节点分解需要 n−2次交换，所以第三层总的交换次数是 n∗(n−1)∗(n−2)n∗(n−1)∗(n−2)。第 kk 层总的交换次数就是 n∗(n−1)∗(n−2)∗…∗(n−k+1)。最后一层为n∗(n−1)∗(n−2)∗…∗2∗1等于 n!。也就是说，全排列的递归算法的时间复杂度大于O(n!)，小于 O(n∗n!)。
小结
有些代码比较适合用递推公式来分析，比如归并排序的时间复杂度、快速排序的最好情况时间复杂度；有些比较适合采用递归树来分析，比如快速排序的平均时间复杂度。而有些可能两个都不怎么适合使用，比如二叉树的递归前中后序遍历。