接上一篇文章「数据结构 - 预备知识 1」

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

如下代码:

/*
    n 为数组长度
    x 为要查找的元素
*/
int f(int[] array, int n, int x) {
    int i = 0;
    int pos = -1;
    for (; i < n; ++i) {
        if (array[i] == x)
            pos = i;
    }
    return pos;
}

这段代码的复杂度为 $O(n)$,在数组中查找一个数据,不一定要把数组完全遍历一遍,有可能中途甚至第一个就找到了。所以这段代码写得不高效,修改后如下:

int f(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)$ 了,因为要查找的变量 x 可能出现在数组的任意位置。存在的情况如下:

  • 如果数组的第一个位置正好是要查找的元素,复杂度为 $O(1)$
  • 如果数组中不存在要查找的元素,需要把数组都遍历一遍,复杂度为 $O(n)$

以上两种情况就正好说明了 最好情况时间复杂度(在最理想的情况下)最坏情况时间复杂度(在最糟糕的情况下)

平均情况时间复杂度

上述的最好、最坏情况,都是在极端情况下的代码复杂度,发生的概率不是太大。所以引入了另外一个概念:平均情况时间复杂度

按照上面的例子:

  1. 在数组 0 ~ n-1 位置中和不在数组中,这两种情况对应的概率统计很麻烦,可以简化,假设假设在数组中与不在数组中的概率都为 $1/2$。
  2. 要查找的数据出现在数组的 0 ~ n-1 的 n 个位置的概率是一样的,为 $1/n$。
  3. 所以,要查找的数据出现在数组 0 ~ n-1 中任意位置的概率是 $1/2n$。

当把每种情况发生的概率都考虑进去,平均时间复杂度计算公式为:
$$1 \times \frac{1}{2n} + 2 \times \frac{1}{2n} + 3 \times \frac{1}{2n} + ··· + n \times \frac{1}{2n} + n \times \frac{1}{2} = \frac{3n+1}{4}$$

这个值是概率论中的加权平均值,也叫期望值。所以,平均时间复杂度的全称应该叫加权平均时间复杂度或期望时间复杂度。

上面的代码的加权平均值为 $(3n+1)/4$,用 $O$ 表示法表示,去掉系数和常量,加权平均时间复杂度是 $O(n)$。

在大多数情况下,并不需要区分最好、最坏、平均情况时间复杂度。一般情况下,使用一个复杂度就可以。只有同块代码在不同的情况下,时间复杂度有量级的差距,才会使用这三种复杂度表示法来区分。

均摊时间复杂度

在代码执行的所有复杂度情况中,绝大多数是低级别的复杂度,个别情况是高级别复杂度,且发生具有一定的时序关系。针对这种特殊场景的复杂度分析,不需要像平均复杂度分析方法一样找出所有的情况及相应的发生概率,然后再计算加权平均值。

针对这种特殊的场景,采用更简单的分析方法:摊还分析法。这分析方法是将高级别复杂度均摊到低级别复杂度中,得到的时间复杂度叫:均摊时间复杂度

常用的应用场景:

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

均摊时间复杂度可以认为是一种特殊的平均时间复杂度,但在实际运用中,不用特意区别它们。分析得到的结果叫平均或均摊,只是个说法,并不重要。