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

Love The Way You Lie 2021-10-18 06:48 283阅读 0赞

> 前一篇文章[算法复杂度分析][Link 1]讲述了复杂度的大 O 表示法和几个分析原则，这篇文章我们来讲讲另外几种复杂度，最好情况时间复杂度（best case time complexity）、最坏情况时间复杂度（worst case time complexity）、平均时间复杂度（average case time complexity）和均摊时间复杂度（amortized time complexity）。

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

顾名思义，这两种时间复杂度指的是特殊情况下的时间复杂度。我们看下面的例子：

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

这段代码实现的功能是，在数组 array 中寻找变量 x 第一次出现的位置，若没有找到，则返回 -1；否则返回位置下标。

用上一篇文章的方法显然是无法分析这段代码的复杂度的。因为，不同情况下的时间复杂度是不同的。当数组中第一个元素就是要找的 x 时，时间复杂度是 O(1)；而当最后一个元素才是 x 时，时间复杂度则是 O(n)。

为了表示代码在不同情况下的时间复杂度，就需要引入三个概念：最好情况时间复杂度、最坏情况时间复杂度和平均情况时间复杂度。

**其中，最好情况时间复杂度就是在最理想情况下执行代码的时间复杂度，它的时间是最短的；最坏情况时间复杂度就是在最糟糕情况下执行代码的时间复杂度，它的时间是最长的。**

## 二、平均情况时间复杂度 ##

最好、最坏时间复杂度反应的是极端条件下的复杂度，发生的概率不大，不能代表平均水平。那么为了更好的表示平均情况下的算法复杂度，就需要引入平均时间复杂度。

继续用前面 find 函数为例，假设变量 x 在和不在数组 array 中的概率分别为 1 / 2；当存在于数组中时，在每个位置的概率均等，为 1 / n。那么，平均情况时间复杂度就可以用下面的方式计算：

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

这个值就是概率论中的加权平均值，也叫期望值。所以平均情况时间复杂度也叫加权平均时间复杂度或期望时间复杂度。可见，find 函数的平均时间复杂度为 O(n)。

大多数情况下，不需要区分最好、最坏、平均情况时间复杂度，只用一个复杂度就可以满足需求了。只有当同一块代码在不同情况下，时间复杂度有数量级上的区别时，才需要考虑这三种复杂度。

## 三、均摊时间复杂度 ##

由上面我们可以知道，平均时间复杂度只有在某些特殊的时候才会用到。均摊时间复杂度的应用场景比它更为特殊。均摊时间复杂度是指，当大部分情况下时间复杂度都很低，只有个别情况下时间复杂度比较高时，并且这些操作之间存在着前后连贯的时序关系，这时候，可以将较高时间复杂度的操作耗时均摊至时间复杂度较低的操作上。这种分析方法叫做摊还分析法，得到的复杂度叫做均摊时间复杂度。

而且，在能够应用均摊时间复杂度分析的场合，一般均摊时间复杂度就等于最好情况时间复杂度。

例如：

int[] array = new int(n);
    int count = 0;
    
    void addLast (int val) {
        if (count == array.length) {
            int[] newArray = new int(2 * n);
            for (int i = 0; i < 2 * n; i++) {
                newArray[i] = array[i];
            }
            newArray[count] = val;
            array = newArray;
        } else {
            array[count] = val
        }
        count++;
    }

这段代码实现的功能是往数组的末尾增加一个元素，如果数组没有满，直接往后面插入元素；如果数组满了，即 `count == array.length`，则将数组扩容一倍，然后再插入元素。

例如，数组长度为 n，则前 n 次调用 addLast() 复杂度都为 O(1)；第 n + 1 次则需要先进行 n 次元素转移操作，然后再进行 1 次插入操作，复杂度为 O(n)。而且很容易看出，O(1) 复杂度的操作和 O(n) 复杂度的操作出现频率是有规律的，每 n 次 O(1) 操作后会跟随一个 O(n) 操作。

那么，就可以将 O(n) 操作的复杂度均摊至每次 O(1) 操作中，均摊下来，这组操作的需要进行 `(n + n * 1) / (n + 1) = 2n / (n + 1)`次操作，所以均摊复杂度为 O(1)。

[Link 1]: https://blog.csdn.net/haoxin963/article/details/90113847