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

继续来看四个复杂度分析方面的知识点:最好情况时间复杂度 (Best Case Time Complexity)、最坏情况时间复杂度 (Worst Case Time Complexity)、平均情况时间复杂度 (Average Case Time Complexity)、均摊时间复杂度 (Amortized Time Complexity)。

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

例如在一个无序数组array查找变量x出现的位置

// 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(1)
  • 最坏情况时间复杂度:在最糟糕的情况下,执行这段代码的时间复杂度,这里为O(n)

2. 平均情况时间复杂度

还是上面的例子:要查找变量x在数组中的位置,有n+1种情况:在数组的0 ~ n-1位置中不在数组中。我们把每种情况下,查找需要遍历的元素个数累加起来,然后再除以n+1,就可以得到需要遍历的元素个数的平均值,即:

平均时间复杂度
平均时间复杂度

简化后得到的平均时间复杂度O(n)

然而上面的考虑还不够全面:若假设变量x在数组中与不在数组中的概率都为1/2,则可得加权平均时间复杂度或者期望时间复杂度

加权平均时间复杂度
加权平均时间复杂度

去掉系数和常量,这段代码的加权平均时间复杂度仍为O(n)

3. 均摊时间复杂度

大部分情况下,我们并不需要区分最好、最坏、平均三种复杂度。平均复杂度只在某些特殊情况下才会用到,而均摊时间复杂度应用的场景比它更加特殊、更加有限。

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

这段代码实现了一个往数组中插入数据的功能。当数组满了之后,用for循环遍历数组求和,并清空数组,将求和之后的sum放到数组的第一个位置,然后再将新的数据插入。但如果数组一开始就有空间空间,则直接将数据插入数组

  • 最好情况O(1)
  • 最坏情况O(n)
  • 平均复杂度O(1)
上述代码的加权平均时间复杂度
上述代码的加权平均时间复杂度

还是insert()函数这个例子:随着n的不断增长,可以发现每一次O(n)的插入操作都会跟着n-1O(1)的插入操作。所以把耗时多的那次操作均摊到接下来的n-1次耗时少的操作上,这一组连续的操作均摊时间复杂度就是O(1)。这就是均摊分析(又称摊还分析)的大致思路。

简单来看,均摊时间复杂度就是一种特殊的平均时间复杂度

参考文章

  1. 数据结构与算法之美 | 极客时间