数据结构笔记04-复杂度分析（下）

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

---

样例代码：

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

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

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

最好情况时间复杂度就是，在最理想的情况下，执行这段代码的时间复杂度。当x正好是数组的第一个元素，这个$O(1)$就是最好情况时间复杂度。

最坏情况时间复杂度就是，在最糟糕的情况下，执行这段代码的时间复杂度。当x正好是数组的最后一个元素，这个$O(n)$就是最坏情况时间复杂度。

平均情况时间复杂度

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

$\frac{1+2+3+...+n+n}{n+1}=\frac{n(n+3)}{2(n+1)}$

时间复杂度的大$O$标记法中，可以省略掉系数、低阶、常量，所以平均时间复杂度就是$O(n)$。

但是其实上面的计算过程稍微有点问题，因为n+1种情况出现的概率不同。如果我们把每种情况发生的概率考虑进去，假设在数组中和不在数组的概率都为1/2，要查找的数据出现在0~n-1的概率是一样的，为1/n，计算公式就变成了这样：

$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}$

这个值就是概率中的加权平均值，也叫作期望值，所以平均情况时间复杂度的全称应该是加权平均时间复杂度或者期望值时间复杂度。引入概率之后，用大$O$表示法来表示，这段代码的平均情况时间复杂度仍然是$O(n)$。

大部分情况下，我们使用一个复杂度就可以满足需求了，只有同一块代码在不同情况下，时间复杂度有量级的差距，我们才会用这三种复杂度表示法来区分。

均摊时间复杂度

// array表示一个长度为n的数组
// 代码中的array.length就等于n
int[] array = 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;
}

这段代码实现了一个往数组中插入数据的功能。当数组满了，清空数组，求和后的sum值放到第一个位置，再插入新的数据。如果一开始就有空闲空间，则直接插入。

这段代码的时间复杂度又是多少呢？

最好复杂度：数组有空闲空间，直接插入，所以是$O(1)$；最坏复杂度：数组已满，先做一次数组求和，所以是$O(n)$

平均复杂度：假设数组长度是n，根据插入位置不同，我们有n种情况，每种情况复杂度为$O(1)$，还有一种额外的情况，数组已满，时间复杂度为$O(n)$，这n+1中情况发生的概率一样，都是1/(n+1)。所以，根据加权平均的计算方法，平均复杂度：

$1\times\frac{1}{n+1}+1\times\frac{1}{n+1}+...+1\times\frac{1}{n+1}+n\times\frac{1}{n+1}=O(1)$

但是，其实这个例子里的平均复杂度分析不需要这么复杂，不需要引入概率论。对比一下这个insert()和前面那个find()的例子，有以下区别：

1. insert()在大部分情况下，时间复杂度都为$O(n)$，只有个别情况下，复杂度才比较高，为$O(n)$;
2. insert()函数，$O(1)$时间复杂度的插入和$O(n)$时间复杂度的插入，出现的概率是非常有规律性的，而且有一定的前后顺序，一个$O(n)$的插入，紧跟着n-1个O(1)​的插入

针对这种特殊的场景，可以引入一种更简单的分析方法：摊还分析法，通过摊还分析法得到的时间复杂度叫均摊时间复杂度。

分析过程：在这个数组中插入数据的例子，每一次$O(n)$的插入操作，都会跟着n-1次$O(1)$的插入操作，所以把耗时多的那次操作平均摊到接下来的n-1次耗时少的操作上，均摊下来，这一组连续操作的时间复杂度就是$O(1)$。

均摊时间复杂度和摊还分析应用场景比较特殊，在能够应用均摊时间复杂度的场合，一般均摊时间复杂度等于最好时间复杂度。个人认为，均摊时间复杂度就是一种特殊的平均时间复杂度，我们应该掌握的是它的分析方法，摊还分析。