递归树

递归的思想就是，将大问题分解为小问题来求解,直到问题的数据规模被分解得足够小，不用继续递归分解为止。如果我们把这个一层一层的分解过程画成图，它其实就是一棵树,叫作递归树。

把归并排序画成递归树，就是下面这个样子：

归并算法中比较耗时的是归并操作，也就是把两个子数组合并为大数组。从图中我们可以看出，每一层归并操作消耗的时间总和是一样的，跟要排序的数据规模有关。我们把每一层归并操作消耗的时间记作 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。

因为每次分区并不是均匀地一分为二，所以递归树并不是满二叉树。

递归树中最短的一个路径每次都乘以 101 ，最长的一个路径每次都乘以 109 。通过计算，我们可以得到，从根节点到叶子节点的最短路径是 log10 n，最长的路径是 log910 n。

所以，遍历数据的个数总和就介于 nlog10 n 和 nlog910 n 之间。根据复杂度的大 O 表示法，对数复杂度的底数不管是多少，我们统一写成 logn，所以，当分区大小比例是 1:9 时，快速排序的时间复杂度仍然是 O(nlogn)。

当 k=99 的时候，树的最短路径就是 log100 n，最长路径是 log99100 n，所以总遍历数据个数介于 nlog100 n 和 nlog99100 n 之间。尽管底数变了，但是时间复杂度也仍然是 O(nlogn)。

也就是说，对于 k 等于 9，99，甚至是 999，9999……，只要 k 的值不随 n 变化，是一个事先确定的常量，那快排的时间复杂度就是 O(nlogn)。所以，从概率论的角度来说，快排的平均时间复杂度就是 O(nlogn)。

实战二：分析斐波那契数列的时间复杂度

1
2
3
4
5
int f(int n) {
  if (n == 1) return 1;
  if (n == 2) return 2;
  return f(n-1) + f(n-2);
}

如果每次都是 −1，那最长路径大约就是 n；如果每次都是 −2，那最短路径大约就是 n/2 。

每次分解之后的合并操作只需要一次加法运算，我们把这次加法运算的时间消耗记作 1。所以，从上往下，第一层的总时间消耗是 1，第二层的总时间消耗是 2，第三层的总时间消耗就是 22。依次类推，第 k 层的时间消耗就是 2k−1，那整个算法的总的时间消耗就是每一层时间消耗之和。

如果路径长度都为 n，那这个总和就是 2^n
如果路径长度都是 n/2 ，那整个算法的总的时间消耗就是 2^(n/2) −1。

所以，这个算法的时间复杂度就介于 O(2^n) 和 O(2^n/2 ) 之间。虽然这样得到的结果还不够精确，只是一个范围，但是我们也基本上知道了上面算法的时间复杂度是指数级的，非常高。

实战三：分析全排列的时间复杂度

“如何把 n 个数据的所有排列都找出来”

如果我们确定了最后一位数据，那就变成了求解剩下 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)}。

递推公式改写成代码逻辑比较复杂，复杂度比较难分析

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
// 调用方式：
// 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-2) +… + n(n-1)(n-2)…21

这个公式的求和比较复杂，我们看最后一个数，n∗(n−1)∗(n−2)∗…∗2∗1 等于 n!，而前面的 n−1 个数都小于最后一个数，所以，总和肯定小于 n∗n!，也就是说，全排列的递归算法的时间复杂度大于 O(n!)，小于 O(n∗n!)，虽然我们没法知道非常精确的时间复杂度，但是这样一个范围已经让我们知道，全排列的时间复杂度是非常高的。

1 个细胞的生命周期是 3 小时，1 小时分裂一次。求 n 小时后，容器内有多少细胞？请你用已经学过的递归时间复杂度的分析方法，分析一下这个递归问题的时间复杂度。

f(0)=1
f(1)=1+1
f(2)=1+1+2=4
时间:3-2-1小时（第一个死掉，整体左移）
f(3)=1+2+4=7
f(4)=2+4+7=13
f(5)=4+7+13=24
f(6)=7+13+24=44

f(n)=2f(n-1)-f(n-4)

与斐波那契数列的递归复杂度相同。(指数级)

如果每次都是 −1，那最长路径大约就是 n；如果每次都是 −4，那最短路径大约就是 n/4 。

时间复杂度就介于 O(2^n) 和 O(2^n/4 ) 之间