3. 复杂度分析：最好、最坏、平均、均摊时间复杂度

最好、最坏时间复杂度

// 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;
  }
  return pos;
}

这段代码，主要是为了查找x在数组中的位置，如果不存在就返回-1。这段代码的时间复杂度是O(n)。接下来我们优化一下上面的代码:

// 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;
}

这个时候，时间复杂度还是O(n)吗？不能确定。如果我们在第1次查询的时候就查到了x，那么就不需要查找剩余的n-1个元素，那么时间复杂度就是O(1)。但是如果数组中不存在x，那么就需要遍历数组，时间复杂度为O(n)。所以不同情况下，时间复杂度不同。

「最好时间复杂度」: 在最理想的情况下，执行这段代码的时间复杂度。就如刚刚查找第一个元素就刚好是x。

「最坏时间复杂度」: 在最糟糕的情况下，执行这段代码的时间复杂度。就如刚刚在数组中不存在x。

平均时间复杂度
上述中，最好和最坏时间复杂度，都是比较极端的情况。这里我们来说说「平均时间复杂度」。
还是以上述那个例子。

要查找变量x，有n+1种情况：在数组的0~n-1位置中和不在数组中。我们把每种情况下，查找需要遍历的元素个数累计起来，然后再除以n+1，就可以得到需要遍历的元素个数的平均值。

(1+2+3+...+n+n) / ( n + 1) = n * ( n + 3) / 2( n + 1)

我们知道，时间复杂度计算中，可以省略掉系数，低阶，常量，所以这个时间复杂度简化之后就是O(n)。

这个结论虽然是正确的，但是计算过程有点问题。我们讲的n+1种情况，出现的概率不是一样的。

我们知道要查找x，要么在数组里，要么不在数组里。我们假设两者概率都为1/2。另外0到n-1位置的概率都是一样的，为1/n。所以根据乘法法则，0到n-1位置的概率都为1/2n。

因此在前面的计算中，没有考虑概率的问题。如果我们考虑概率问题进去，就变成：

image.png

引入概率后，这段代码的平均时间复杂度为(3n+1)/4。用大O表示法，也是O(n)。

均摊时间复杂度

 // 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;
 }

这段代码的主要功能：这段代码实现了一个往数组中插入数据的功能。当数组满了之后，也就是代码中的 count == array.length 时，我们用 for 循环遍历数组求和，并清空数组，将求和之后的 sum 值放到数组的第一个位置，然后再将新的数据插入。但如果数组一开始就有空闲空间，则直接将数据插入数组。

运用上面叙述的最好，最坏，平均时间复杂度来分析：

最好的情况下，就是第一个位置就是空闲的直接插入，时间复杂度O(1)。

最坏的情况下，就是没有空闲的位置，遍历计算了数组后插入，时间复杂度O(n)。

平均时间复杂度，「n个空闲位置」和「没有空闲位置」一共n+1种情况。

image.png

对于 insert() 函数来说，O(1) 时间复杂度的插入和 O(n) 时间复杂度的插入，出现的频率是非常有规律的，而且有一定的前后时序关系，一般都是一个 O(n) 插入之后，紧跟着 n-1 个 O(1) 的插入操作，循环往复。

所以，针对这样一种特殊场景的复杂度分析，我们并不需要像之前讲平均复杂度分析方法那样，找出所有的输入情况及相应的发生概率，然后再计算加权平均值。针对这种场景，我们使用「摊还分析法」。

如果使用摊还分析法来分析时间复杂度？

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

对一个数据结构进行一组连续操作中，大部分情况下时间复杂度都很低，只有个别情况下时间复杂度比较高，而且这些操作之间存在前后连贯的时序关系，将较高时间复杂度那次操作的耗时，平摊到其他那些时间复杂度比较低的操作上。而且，在能够应用均摊时间复杂度分析的场合，一般均摊时间复杂度就等于最好情况时间复杂度。