1. 分析每一步核心操作的时间复杂度
  2. 分析树高：最大树高和最小树高
  3. 计算每层复杂度，全加起来

实战1:快速排序

  1. 分割算法是O(n)
  2. 树高最大最小都是 logn，所以O(logn)

实战2：斐波那契数列:

  1. 加和算法1
  2. 节点数为倍增。 通项为2^h
  3. 高度最高n，最低n/2.相当于求等比数列前n项和。所以结果2^n,指数级

实战3:全排列

  1. 核心为将每一项交换到最后一个位置，O（n）
  2. 每层树枝-1，所以每层通项是n*n-1*n-2...n-h。
  3. 最后一层为一个，所以是n！。求和不好求但是知道该算法大于n！

思考题：

1 个细胞的生命周期是 3 小时，1 小时分裂一次。求 n 小时后，容器内有多少细胞？请你用已经学过的递归时间复杂度的分析方法，分析一下这个递归问题的时间复杂度。
思路：f(n) = 2 * f(n-1) - 【n时刻点死掉的细胞数量】
而在【n时刻点死掉的细胞数量】就是【n-3时刻点新分裂的细胞数量】;【n-3时刻点新分裂的细胞数量】就是【n-4时刻点的细胞数总数】，即f(n-4)

故递推公式：f(n) = 2 * f(n-1) - f(n-4)，类似斐波那契数列，为指数级