最好、最坏、平均 、均摊时间复杂度

较为复杂的分析方法大致可分为四类、分别为：最好时间复杂度、最坏时间复杂度、平均时间复杂度和均摊时间复杂度。

这里有一段代码，针对它下面分别来说一下怎么算着四种时间复杂度。

// i的取值范围是 0～n
void add(int element) {
  if (i >= len) {
    int new_array[] = new int[len*2];
    for (int j = 0; j < len; ++j) {
      new_array[j] = array[j];
    }
    array = new_array;
    len = 2 * len;
  }
  array[i] = element;
  ++i;
}

最好、最坏时间复杂度

最好时间复杂度，言明直意，就是在最好情况下求得的时间复杂度，对于上面代码，针对长度为N的数组添加一个元素的最好时间复杂度为O（1）

在最好情况下，数组空间很充足，可以直接将数组添加到第i位置

在最坏情况下，数组空间不够，所以要重新申请一个2倍大小的数组空间，把原来array数组中的数据依次copy到new_array，因此最坏的时间复杂度应该是O（N）

平均时间复杂度

最好、坏的时间复杂度局限性很大，有时不能准确说明问题，针对这种情况，我们用代码执行各种情况的加权平均值来说明问题。

假设数组的大小为N，i的取值范围为0～N，在0～n-1时间复杂度为O（1），在i等于N的时候时间复杂度为O（N），i的取值有1/（n-1）种可能性，所以有：

最终平均时间复杂度是O（1）

均摊时间复杂度

网上有好多说平均时间复杂度就是均摊时间复杂度，它们并没有什么区别，不管他们俩是否一样，这边有两个tip来帮助我们算出均摊时间复杂度

1. 在N种情况中，如果第被低阶复杂度占去了半壁江山，那么通过均摊更高阶的复杂度到低阶上，最终结果为低阶复杂度。
2. 假如你发现低阶复杂度和高阶复杂度出现规律性的交替，那么通常最终结果为低阶复杂度。

根据上面的tips。很快就得出它的均摊时间复杂度为O（1）

为什么要引入这4种复杂度？

一般我们用不到到这些分析方法，针对某些场景，如果普通的分析方法不能论证我们的论点，那么使用它们往往可以使论点更具有说服力。