如何借助树来求解递归算法的时间复杂度？

递归树与时间复杂度分析

如果我们把这个一层一层的分解过程画成图，它其实就是一棵树。我们给这棵树起一个名字，叫作递归树。

实战一：分析快速排序的时间复杂度

快速排序的过程中，每次分区都要遍历待分区区间的所有数据，所以，每一层分区操作所遍历的数据的个数之和就是 n。我们现在只要求出递归树的高度 h，这个快排过程遍历的数据个数就是 h∗n ，也就是说，时间复杂度就是 O(h∗n)。因为每次分区并不是均匀地一分为二，所以递归树并不是满二叉树。

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

f(n) 分解为 f(n−1) 和 f(n−2)，每次数据规模都是 −1 或者 −2，叶子节点的数据规模是 1 或者 2。所以，从根节点走到叶子节点，每条路径是长短不一的。如果每次都是 −1，那最长路径大约就是 n；如果每次都是 −2，那最短路径大约就是 2n。

如果路径长度都为 n，那这个总和就是 2n−1。

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

所以，这个算法的时间复杂度就介于 O(2n) 和 O(22n) 之间。

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

python代码

def permutations(arrays, position, end):
    if position == end:
        print(arrays)
    else:
        for index in range(position, end):
            arrays[index], arrays[position] = arrays[position], arrays[index]
            permutations(arrays, position+1, end)
            arrays[index], arrays[position] = arrays[position], arrays[index]

全排列时间复杂度大于O(n!) 小于 O(n*n!)

思考

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

2*f(n-1) + f(n-4) # 注意需要减去的是新生的细胞