【数据结构与算法之美】递归树：如何借助树来求解递归算法的时间复杂度？（细胞分裂问题）

一、递归树与时间复杂度分析

1.递归思想就是将大问题分解为小问题来求解，然后在将小问题分解为小小问题，将问题一层一层地分解，直到问题的数据规模被分解得足够小，不要继递归分解为止。

2.用递归树来求解归并排序的时间复杂度

①：每次分解是一分为二，所以代价很低，将时间上的消耗记作常量1。
②：归并算法中比较耗时的归并操作，也就是把两个子数组合并为大数组
③：每一层归并操作消耗的时间总和是一样的，跟要排序的数据规模有关，将每层归并操作消耗的时间记作n。
④：我们只需要知道这颗树的高度h,用高度乘以每层的时间消耗n,就可以得到总的时间复杂度O(n*h)。
⑤：从归并排序的原理和递归树，可知归并排序递归树是一颗满二叉树，满二叉树的高度大约为log2n，所以归并排序递归实现的时间复杂度就是O(nlogn)。

二、分析快速排序的时间复杂度

①：快速排序在最好情况下，每次分区都能一份为二，这个时候用递归公式T(n)=2T(n/2)+n，可以推导出时间复杂度是O(nlogn)。
②：但并不是总能非常平均的分区，所以通过公式推导时间复杂度会非常复杂。
③：快速排序的过程中，每次分区都要遍历待分区区间的所有数据，所以，每一层分区操作所遍历的数据的个数之和就是n。只要求出递归树的高度h，这个快排过程遍历的数据个数就是h*n，即时间复杂度就是O(h*n)。
④：因为每次分区并不是均匀地一分为二，所以递归树并不是满二叉树。
⑤：因为快速排序结束的条件是待排序的小区间，大小为1，即叶子节点里的数据规模是1。
⑥：从根节点n到叶子节点1，递归树中最短的一个路径每次都乘以1/10，最长的一个路径每次都乘以9/10。
⑦：通过计算，从根节点到叶子点最短路径是log10n,最长的路径是log10/9 n。
 ⑧：遍历数据的个数总和就介于nlog10n和nlog10/9 n之间。根据复杂度O表示法规则，当分区大小比例是1:9时，快速排序的时间复杂度仍然是O(nlogn)。

三：斐波那契数列的时间复杂度

 ①：f(n)分解为f(n-1)和f(n-2)，每次数据规模都是-1或-2，叶子节点的数据规模是1或2。所以从根节点走到叶子节点，每条路径是长短不一的。
②：如果每次都是-1，那最长路径大约就是n；如果每次都是-2，那最短路径大约就是n/2。
③：第k层的时间消耗是2(^k-1)，总时间消耗之和是2^n -1

四：分析全排列的时间复杂度

n + n*(n-1) + n*(n-1)*(n-2) +... + n*(n-1)*(n-2)*...*2*1

五、课后思考

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

比如0小时的时候，培养皿中放入1个细胞，1小时的时候分裂成2个，2小时的时候分裂成4个，3小时本来分裂成8个，但是最先的1个本体已经分裂了3次，它死掉，最终剩下7个。下面是列举的时间以及对应的细胞数：
0 1 2 3
1 2 4 7

n = 0，f(0) = 1

n = 1，f(1) = 2*f(0)

n = 2，f(2) = 2*f(1)

n = 3，f(3) = 2*f(2)

n = 4，f(4) = 2*f(3) - f(0)，减去存活了3个小时的细胞个数=n-3时刻新生的细胞数=前一时刻分裂而来的即f(n-4)

将n个小时的细胞数定义为f(n)，像这种知道f(0)，f(1)，f(2)...，要你推算f(n)的题目，是面试的时候经常遇到的一类题目。f(n)的结果与前面已知的f(n-1)或者f(n-2)...f(n-k)有关，重点是要找出f(n)的递推公式，有了递推公式之后，可以很容易用递归来实现，就像斐波拉契数列f(n)=f(n-1)+f(n-2)用递归来实现类似。

回到这一题，细胞分裂分成两个步骤，先分裂，再死亡。比如第4小时，先从3小时的7个细胞分裂即乘2为14个，然后计算死亡的细胞，直观上来说我们会认为第1小时的细胞此时分裂了3次，会死掉，最终是7x2-2=12个细胞，得到公式f(n)=f(n-1)x2-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)x2-f(n-4)。

int GetCellCount(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 GetCellCount(n-1) * 2 - GetCellCount(n-4);
|