原文链接:https://time.geekbang.org/column/intro/100017301
27 | 递归树
如何借助树来分析归并排序算法的时间复杂度？
每次分解一分为二，代价很低，时间上消耗记作O(1)。
每一层合并消耗时间相同，和数据规模相关，记作 O(n)。
归并排序递归树是一颗满二叉树，高度为 log2n。
归并排序时间复杂度：O(n logn)。
如何借助树来分析快速排序算法的时间复杂度？
平均情况：1 : k
k = 9 时。
每一层遍历 n 个元素。
快速排序结束条件：叶子节点 1 个元素。
根节点 n 个元素到叶子节点 1 个元素最短路径每一层乘 1 /10，最长路径每一层乘 9 / 10。
根节点到叶子节点最短路径：log10n，最长路径 log(10 / 9 ) n。
遍历个数在 n * log10 到 n * log(10 / 9 ) n 之间，快速排序时间复杂度为：O(n logn)。
k 的值不随 n 改变，对最终时间复杂度无影响。
如何借助递归树来分析斐波那契数列的时间复杂度？
f(n) 分解为 f(n - 1) 和 f(n - 2)，每次数据规模 -1 或 -2，叶子节点数据规模是 1 或者 2。
根节点到叶子节点最长为 n ，最短为 n / 2。
合并的操作只需要一次加法运算，耗时记作 O(1)。
每一层消耗时间为 2^ (k - 1) ，路径长度为 n 总和为 2^n - 1。
路径长度为 n 总和为 2^(n / 2) - 1。
时间复杂度为指数级别。
如何借助递归树来分析全排列的时间复杂度？
最后一位有 n 种情况，求解 n 个 “n - 1数据的排列” 的子问题。
递推公式：
假设数组中存储的是1，2， 3...n。
f(1,2,...n) = {最后一位是1, f(n-1)} + {最后一位是2, f(n-1)} +...+{最后一位是n, f(n-1)}。
第一层有 n 此交换，第二层有 n (n - 1) 次交换，第三层有 n(n - 1)(n - 2) 此交换，最后一层有 n(n - 1)(n - 2) *…21 次交换。
总交换次数：
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 * n!，全排列递归时间复杂度大于O(n!)，小于O(n * n!)。时间复杂度非常高。
1 个细胞的生命周期是 3 小时，1 小时分裂一次。求 n 小时后，容器内有多少细胞？如何分析递归时间时间复杂度？
需要重新系统完整的分析。