最好、最坏情况时间复杂度指的是特殊情况下的时间复杂度。
动图表明的是在数组 array 中寻找变量 x 第一次出现的位置，若没有找到，则返回 -1；否则返回位置下标。
1int find(int[] array, int n, int x) {2 for ( int i = 0 ; i < n; i++) {
3 if (array[i] == x) {
4 return i;
5 break;
6 }
7 }
8 return -1;
9}
在这里当数组中第一个元素就是要找的 x 时，时间复杂度是 O(1)；而当最后一个元素才是 x 时，时间复杂度则是 O(n)。
最好情况时间复杂度就是在最理想情况下执行代码的时间复杂度，它的时间是最短的；最坏情况时间复杂度就是在最糟糕情况下执行代码的时间复杂度，它的时间是最长的。
平均情况时间复杂度最好、最坏时间复杂度反应的是极端条件下的复杂度，发生的概率不大，不能代表平均水平。那么为了更好的表示平均情况下的算法复杂度，就需要引入平均时间复杂度。
平均情况时间复杂度可用代码在所有可能情况下执行次数的加权平均值表示。
还是以 find 函数为例，从概率的角度看， x 在数组中每一个位置的可能性是相同的，为 1 / n。那么，那么平均情况时间复杂度就可以用下面的方式计算：
((1 + 2 + … + n) / n + n) / 2 = (3n + 1) / 4
find 函数的平均时间复杂度为 O(n)。
均摊复杂度分析我们通过一个动态数组的 push_back 操作来理解 均摊复杂度。
1template <typename T>2class MyVector{
3private:
4 T* data;
5 int size; // 存储数组中的元素个数
6 int capacity; // 存储数组中可以容纳的最大的元素个数
7 // 复杂度为 O(n)
8 void resize(int newCapacity){
9 T *newData = new T[newCapacity];
10 for( int i = 0 ; i < size ; i ++ ){
11 newData[i] = data[i];
12 }
13 data = newData;
14 capacity = newCapacity;
15 }
16public:
17 MyVector(){
18 data = new T[100];
19 size = 0;
20 capacity = 100;
21 }
22 // 平均复杂度为 O(1)
23 void push_back(T e){
24 if(size == capacity)
25 resize(2 * capacity);
26 data[size++] = e;
27 }
28 // 平均复杂度为 O(1)
29 T pop_back(){
30 size --;
31 return data[size];
32 }
33
34};
push_back实现的功能是往数组的末尾增加一个元素，如果数组没有满，直接往后面插入元素；如果数组满了，即 size == capacity ，则将数组扩容一倍，然后再插入元素。
例如，数组长度为 n，则前 n 次调用 push_back 复杂度都为 O(1) 级别；在第 n + 1 次则需要先进行 n 次元素转移操作，然后再进行 1 次插入操作，复杂度为 O(n)。
因此，平均来看：对于容量为 n 的动态数组，前面添加元素需要消耗了 1 * n 的时间，扩容操作消耗 n 时间 ，
总共就是 2 * n 的时间，因此均摊时间复杂度为 O(2n / n) = O(2)，也就是 O(1) 级别了。