1 最好、最坏情况时间复杂度

• 最好时间复杂度：在最理想的情况下，执行这段代码的时间复杂度。
• 最坏时间复杂度：最坏情况时间复杂度就是，在最糟糕的情况下，执行这段代码的时间复杂度。

在实际的运用场景中，代码往往是没有那么简单的。我在这里以代码的方式来具体的讲解最好、最坏情况时间复杂度情况。

// n表示数组array的长度
int find(int[] array, int n, int x) {
  int i = 0;
  int pos = -1;
  for (; i < n; ++i) {
    if (array[i] == x) {
       pos = i;
       break;
    }
  }
  return pos;
}

在以上的代码中，具体的代码逻辑是查找指定的元素是否包含在数组中，若没有则返回-1，若存在则直接返回数组下标。因为，要查找的变量 x 可能出现在数组的任意位置。

如果数组中第一个元素正好是要查找的变量 x，那就不需要继续遍历剩下的 n-1 个数据了，那时间复杂度就是 O(1)，即最好时间复杂度。

但如果数组中不存在变量 x，那我们就需要把整个数组都遍历一遍，时间复杂度就成了 O(n)，即最坏时间复杂度。

2 平均时间复杂度

平均时间复杂度的全称应该叫加权平均时间复杂度或者期望时间复杂度。

3 均摊时间复杂度

均摊时间复杂度就是一种特殊的平均时间复杂度。均摊时间复杂度对应的分析方法：摊还分析（或者叫平摊分析）。

每一次 O(n) 的插入操作，都会跟着 n-1 次 O(1) 的插入操作，所以把耗时多的那次操作均摊到接下来的 n-1 次耗时少的操作上，均摊下来，这一组连续的操作的均摊时间复杂度就是 O(1)。

思考题 求最好、最坏、均摊时间复杂度

// 全局变量，大小为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(n) 的插入操作，都会跟着 n-1 次 O(1) 的插入操作，所以把耗时多的那次操作均摊到接下来的 n-1 次耗时少的操作上，均摊下来，这一组连续的操作的均摊时间复杂度就是 O(1)。