本小节主要讲解了分析时间复杂度的几个点：最好情况的时间复杂度(best case time complexity)，最坏情况的时间复杂度(worst case time complexity)，平均情况的时间复杂度(average case time complexity)，均摊时间复杂度(amortized time complexity)。

最好情况的时间复杂度

最好情况，显然就是当算法中的n取某个值的时候，使得这个算法执行的时间周期最短，就是最好情况的时间复杂度。也就是在最理想的情况下，执行这段代码的时间复杂度。

最坏情况的时间复杂度

最坏情况，显然，就是在最糟糕的情况下，这段代码执行的时间复杂度。

平均情况的时间复杂度

平均情况复杂度，并不是简单的（最好情况+最坏情况）/2 即可。而是需要判断出n的某个取值的概率，然后乘以此时的时间复杂度。得出来的就是平均情况的时间复杂度。

举个例子：对于一个数据规模为n的算法。假设n取每个值的概率为p(i)，当n取值为i的时候的时间复杂度为O(i)，则其这个算法的时间复杂度为：
$\sum_{i=0}^n\p(i)*O(i)$

均摊时间复杂度

首先明确一点，均摊时间复杂度就是平均情况时间复杂度的一种特殊情况。

举个例子：

// array 表示一个长度为 n 的数组
// 代码中的 array.length 就等于 n
int[] array = new int[n];
int count = 0;

void insert(int val) {
  if (count == array.length) {
    int sum = 0;
    for (int i = 0; i < array.length; ++i) {
      sum = sum + array[i];
  }
  array[0] = sum;
  count = 1;
  }
  array[count] = val;
  ++count;
}

这段代码是插入一个数字，当数组中有空闲时候，就直接插入到这个数组中；当数组中没有空闲的时候，把这个数组求和，放到数组的第一个array[0]中，然后把新来的数据插入到后面的数组中。（先不care这个代码是否合理）

显然：最理想情况下，就是数组没有满的时候，时间复杂度为O(1)；最坏的情况，就是当数组满的时候，时间复杂度为O(n)；那么平均呢？假设数组的长度是 n，根据数据插入的位置的不同，我们可以分为 n 种情况，每种情况的
时间复杂度是 O(1)。除此之外，还有一种“额外”的情况，就是在数组没有空闲空间时插入一个数据，这个时候的时间复杂度是 O(n)。而且，这 n+1 种情况发生的概率一样，都是
1/(n+1)。所以，根据加权平均的计算方法，我们求得的平均时间复杂度就是：

平均时间复杂度

但是这种特殊的场景，还有一个更加简单的分析方法：摊还分析法，也叫作均摊时间复杂度。我们还是继续看在数组中插入数据的这个例子。每一次 O(n) 的插入操作，都会跟着 n-1次 O(1) 的插入操作，所以把耗时多的那次操作均摊到接下来的 n-1 次耗时少的操作上，均摊下来，这一组连续的操作的均摊时间复杂度就是 O(1)。这就是均摊分析的大致思路。你都理解了吗？

课后思考

你可以用今天学习的知识，来分析一下下面这个 add() 函数的时间复杂度

// 全局变量，大小为 10 的数组 array，长度 len，下标 i。
int array[] = new int[10];
int len = 10;
int i = 0;

// 往数组中添加一个元素
void add(int element) {
  if (i >= len) { // 数组空间不够了
    // 重新申请一个 2 倍大小的数组空间
    int new_array[] = new int[len*2];
    // 把原来 array 数组中的数据依次 copy 到 new_array
    for (int j = 0; j < len; ++j) {
      new_array[j] = array[j];
    }
    // new_array 复制给 array，array 现在大小就是 2 倍 len 了
    array = new_array;
    len = 2 * len;
  }
  // 将 element 放到下标为 i 的位置，下标 i 加一
  array[i] = element;
  ++i;
}

答案：最好O(1)，最差O(n)，均摊O(1)