#技术派的书架#

在 1.1 节中，我们讲了复杂度的大 O 表示法和分析方法，还举了一些常见复杂度分析的例 子，如 O(1)、O(logn)、O(n) 和 O(nlogn) 复杂度分析。 在本节中，我们继续进行时间复杂度分析，介绍 4 个更加细分的复杂度概念：最好情况时 间复杂度（best case time complexity）、最坏情况时间复杂度（worst case time complexity）、平均 情况时间复杂度（average case time complexity）和均摊时间复杂度（amortized time complexity）

最好时间复杂度和最坏时间复杂

我们在 1.1 节举的分析复杂度的例子都很简单，本节我们来看一个稍微复杂的例子，如下 所示。读者可以用 1.1 节介绍的分析方法，自己先试着分析一下这段代码的时间复杂度。

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

上述代码要实现的功能：在一个无序的数组（array）中，查找变量 x 出现的位置。如 果没有找到，就返回 −1。按照 1.1 节介绍的分析方法，这段代码的复杂度是 O(n)，其中，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.1 节介绍的 分析方法解决不了这个问题。 要查找的变量 x 可能出现在数组的任意位置。如果数组中第一个元素正好等于要查找的 变量 x，就不需要继续遍历剩下的 n−1 个数据了，时间复杂度就是 O(1)。如果数组中不存在 变量 x，那么需要把整个数组遍历一遍，时间复杂度就变成了 O(n)。因此，在不同的情况下， 这段代码的时间复杂度是不一样的。 为了表示代码在不同情况下的不同时间复杂度，我们引入 3 个概念：最好情况时间复杂 度、最坏情况时间复杂度和平均情况时间复杂度。为了方便表述，在平时的开发中，我们往往 把它们简称为：最好时间复杂度、最坏时间复杂度和平均时间复杂度。 顾名思义，最好情况时间复杂度就是：在最好的情况下，执行这段代码的时间复杂度。就 像我们刚刚讲到的，在最好的情况下，要查找的变量 x 正好是数组的第一个元素，这种情况 下对应的时间复杂度就是最好情况时间复杂度 O(1)。 同理，最坏情况时间复杂度就是：在最糟糕的情况下，执行这段代码的时间复杂度。就像 刚举的那个例子，如果数组中没有要查找的变量 x，就需要把整个数组遍历一遍，这种情况下 对应的时间复杂度就是最坏情况时间复杂度 O(n)。

平均时间复杂度

最好时间复杂度和最坏时间复杂度对应的都是极端情况下的时间复杂度，发生的概率其实 并不大。为了更好地表示平均情况下的复杂度，我们需要引入平均时间复杂度这个概念。平均 时间复杂度指的是代码被重复执行无数次，对应的时间复杂度的平均值。平均情况时间复杂度 该怎么分析呢？我们还是借助刚才那个例子来解释。 要查找的变量x在数组中的位置，有n+1种情况：x在数组的0～n−1位置上和不在数组中。 我们把每种情况下需要遍历的元素个数累加起来，然后除以 n+1，就可以得到需要遍历的元素 个数的平均值，即

前面讲到，在用大 O 表示法表示时间复杂度的时候，我们可以省略系数、低阶和常量， 因此，式（1-4）简化之后，得到的平均情况时间复杂度就是 O(n)。 尽管平均时间复杂度是 O(n) 这个结论是正确的，但计算过程稍微有点问题。问题在于： 刚讲的这 n+1 种情况出现的概率并不相同。接下来，我们具体分析一下。这里要用到一些概率 论的知识，不过非常简单。

我们知道，要查找的变量 x，要么在数组里，要么不在数组里。这两种情况出现的概率 都是 1/2。另外，要查找的数据出现在 0 ～ n−1 这 n 个位置的概率也是一样的，为 1/n。因此， 根据概率乘法法则，要查找的数据出现在 0 ～ n−1 中任意位置的概率是 1/(2n)。 前面的推导过程存在的最大问题是没有将各种情况发生的概率考虑进去。如果我们把每种 情况发生的概率也考虑进去，那么平均时间复杂度的计算过程就变成了式（1-5）。

这个值就是概率论中的加权平均值，也称为期望值。因此，平均时间复杂度更准确的描述 应该为加权平均时间复杂度或者期望时间复杂度。 在引入概率之后，加权平均值为 (3n+1)/4。用大 O 复杂度表示法来表示，去掉系数和常 量，仍然是 O(n)，与前面给出的结果相同。 读者可能会认为，平均情况时间复杂度分析真复杂，还涉及概率论的知识。实际上，在大 多数情况下，我们并不需要区分最好时间复杂度、最坏时间复杂度和平均时间复杂度这 3 种情 况。对于 1.1 节中的那些例子，在任何情况下，性能表现都一样，因此我们使用一种复杂度来 表示就足够了。只有当同一段代码在不同情况下性能表现不同，并且时间复杂度有量级的差别 时，我们才会使用这 3 种不同的复杂度来表示。

均摊时间复杂度

下面我们介绍平均时间复杂度的一个特殊情况：均摊时间复杂度。同时，我们会介绍均摊 时间复杂度对应的分析方法：摊还分析法（也称为平摊分析法）。我们还是通过一个具体的例 子来讲解，代码如下所示。

 //array和count是类成员变量或者全局变量 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];}System.out.println(sum);count = 0;}array[count] = val;++count;}

上面这段代码实现了向数组中插入数据的功能。如果数组中有空闲空间，就直接将数据插 入数组。当数组满了之后（count==array.length），用 for 循环遍历数组并求和，同时 清空数组（count 表示数组中元素个数，count=0 就表示清空了数组），然后将新数据插入。 那么 insert() 函数的时间复杂度是多少呢？我们先用刚才介绍的 3 种时间复杂度的分 析方法来分析一下。 在最好的情况下，数组中有空闲空间，此时只需要将数据插入到数组下标为 count 的位 置，因此，最好时间复杂度为 O(1)。在最坏的情况下，数组中没有空闲空间，此时需要先进行一次数组的遍历求和，然后将数据插入，因此，最坏时间复杂度为 O(n)。 那么平均情况时间复杂度是多少呢？这里稍微强调一下，insert() 函数的平均时间复杂 度指的是多次调用这个函数对应的时间复杂度的平均值。对于平均时间复杂度，我们先用前面 提到的概率论的分析方法来分析。 假设数组的长度是 n。当数组中有空闲空间时，插入数据的时间复杂度是 O(1)。根据插入 位置的不同（下标为 0 ～ n−1 的位置），它又分为 n 种情况。除此之外，在数组没有空闲空间时， 插入一个数据需要遍历数组，对应的时间复杂度是 O(n)。这 n+1 种情况发生的概率一样，都是 1/(n+1)。因此，根据加权平均值的计算方法，平均时间复杂度的计算公式如式（1-6）所示。

不过，对于 insert() 函数的平均时间复杂度分析，其实没有这么复杂，并不需要引入 概率论的知识。这是为什么呢？我们对比一下 insert() 函数和前面的 find() 函数，读者就 会发现这两者有很大的差别。 首先，find() 函数在极端情况下，复杂度才为 O(1)。而 insert() 函数在大部分情况下， 时间复杂度为 O(1)，只有在个别情况下，复杂度才比较高，为 O(n)。这是 insert() 函数区 别于 find() 函数的第一个地方。 我们再来看这两个函数第二个不同的地方。对于 insert() 函数，O(1) 时间复杂度的插 入和 O(n) 时间复杂度的插入出现的频率是非常有规律的，有一定的前后时序关系，一般是在 一个 O(n) 时间复杂度的插入之后，紧跟着 n−1 个 O(1) 时间复杂度的插入操作，不断循环。 针对这样一种特殊场景的平均时间复杂度分析，我们可以不用概率论的分析方法，而是引 入一种更加简单的分析方法：摊还分析法。对于通过摊还分析法得到的时间复杂度，我们给它 起了一个更加特殊的名字—均摊时间复杂度。 那么究竟如何使用摊还分析法来分析算法的均摊时间复杂度呢？ 我们还是继续看上面给出的那个例子。每一次 O(n) 时间复杂度的插入操作都会跟着 n−1 次 O(1) 时间复杂度的插入操作，因此，如果我们把耗时多的那次操作的耗时均摊到接下来的 n−1 次耗时少的操作上，那么均摊下来，这一组连续插入操作的均摊时间复杂度就是 O(1)。 均摊时间复杂度和摊还分析法的应用场景比较特殊，因此，它们并不是很常用。为了方便 读者理解、记忆，这里简单总结一下它们的应用场景。 对一个数据结构进行一组连续操作，在大部分情况下，时间复杂度很低，只有个别情况 下，时间复杂度比较高，而且，这些操作之间存在前后连贯的时序关系，这个时候，我们就可 以将这一组操作放在一起分析，观察是否能将较高时间复杂度的那次操作的耗时均摊到其他较 低时间复杂度的操作上。还有，在能够应用均摊时间复杂度分析的场景中，一般均摊时间复杂 度就等于最好时间复杂度。

本文摘自《数据结构与算法之美》

20个经典数据结构与算法，100个真实项目场景案例，300多幅算法手绘图解，一本在手，算法全有，面试大厂不愁！

豆瓣评分9.5，极客时间畅销专栏集结成书，内容更新30%

下一篇数组（上）：为什么数组的下标一般从 0 开始编号喜欢请关注+评论+转发哦