《最好、最坏、平均、均摊时间复杂度》原文链接，阅读体验更佳

不同情况下，时间复杂度可能不同

上一篇文章中，我们总结了算法时间复杂度的大O表示法也就是渐进时间复杂度以及算法时间复杂度分析的基本方法。

事后统计法的缺陷之一就是测试结果受数据规模和数据实际情况的影响很大，但是在上一篇文章中我们给出的所有示例中，输入的数据都是循环的次数。在这种情况下其实只能体现出数据规模对算法效率的影响，但是却不能体现出同规模数据的不同实际情况对算法效率的影响。

还是拿排序算法来说，对于同一个排序算法，即使是我们输入的数据规模是一样的，但是待排序数据的有序度不一样，排序执行时间就会有很大的差异。极端情况下，如果数据已经是有序的，那么排序算法不需要做任何操作，执行时间就会非常短。

可见，对一个算法进行时间复杂度分析的时候，我们也要考虑同规模数据的不同情况对算法效率造成的影响，也就是我们需要对输入数据的具体情况进行分类讨论，才能比较准确地评估一个算法的实际情况，甚至，在数据规模相同的情况下，数据的实际情况会决定我们对算法的选型。

所以，这篇文章我们就来补充一下，如何针对数据的不同情况来对算法的时间复杂度进行分析。

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

我们来看下面一个搜索算法的例子：

int find(int[] array, int value) {
    if(array == null || array.length == 0) {
        return -1;
    }
    for(int i = 0; i < array.length; i++) {
        if(array[i] == value) {
            return i;
        }
    }
    return -1;
}
复制代码

读过上面的代码之后，我们不难发现，上面的代码和上一篇文章中给出的示例不同的是，代码中和数据规模相关的循环代码并不总是能够完全执行，这个时候，我们可以说这段代码的时间复杂度是O(a.length)吗？很显然，并不一定，这个时候我们上一篇文章中介绍的复杂度分析方法就不够用了。

因为，要查找的value可能出现在数组的任意位置，如果数组中第一个元素恰好就是我们要寻找的value，那么第7行代码就会直接返回结果，提前结束对数组的遍历，这个时候的时间复杂度就是O(1)；但是，如果我们不太走运，数组中并没有我们要寻找的value，那么代码就会把整个数组遍历一遍，最后第10行代码返回-1，这个时候的时间复杂度就变成了O(n)。所以，在不同情况下，这段代码的时间复杂度是不一样的。

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

对于前两者，非常好理解，其实我们上面的例子中已经把上面代码的最好情况时间复杂度和最坏情况时间复杂度都分析出来了。

顾名思义，**最好情况时间复杂度，就是在输入数据最理想的情况下，执行这段代码的时间复杂度。**就像我们上面的例子中，在最理想的情况下，数组的第一个元素就是我们要查找的value，这个情况下对应的时间复杂度就是最好情况时间复杂度。

同样的，**最坏情况时间复杂度，就是在最糟糕的情况下，这行这段代码的时间复杂度。**就像我们上面的例子中，如果输入的数组中压根就没有我们要寻找的value，这个时候我们就需要遍历整个数组，这种最糟糕的情况下对应的时间复杂度就是最坏情况时间复杂度。

平均情况时间复杂度

最好情况和最坏情况下的时间复杂度对应的都是极端情况下的代码时间复杂度，发生的概率不大。为了更好地描述更加常规情况下的代码时间复杂度，我们需要引入另一个概念：平均情况时间复杂度。

平均情况时间复杂度应该怎么分析呢？其实就是把每一种情况的时间复杂度乘上对应情况出现的概率然后除以总情况数量，也就是**每种情况下的时间复杂度的加权平均值。**在分析平均情况时间复杂度的时候，就需要使用一点概率论的知识了。

还是以上面的查找算法为例，要查找的变量x在数组中的位置有n+1中情况：在数组中0~n-1的任意一个位置和不在数组中。每种情况下的时间复杂度其实就是需要遍历的元素的个数，分别为1(value在array[0]上的时候)和n(value不存在于数组中时)。我们先假设value出现在每个位置上的概率是一样的，这个时候我们把每种情况下需要查找遍历的元素的个数加起来，然后再除以n+1，就可以得到需要遍历的元素个数的平均值：

而在大O复杂度表示法中，可以省略掉系数、低阶、常量，我们将上面的结果简化之后，得到的平均情况时间复杂度就是O(n)。

上面的结论虽然是正确的，但是推导过程存在一些问题，因为我们上面讲到value存在于数组中的n+1个位置的概率其实是不一样的，实际上它不存在于数组中的概率实际上要大一些。

我们知道，要查找的value，要么在数组中，要么不在数组中。这两种情况对应的概率统计起来比较麻烦，这里为了方便理解，我们就假设value在数组中的概率和不在数组中的概率都是1/2。而当value存在于数组中的时候，它出现在数组中的任意一个位置的概率都是1/n，所以，根据概率的乘法法则，要查找的数据出现在0~n-1中任意位置的概率是1/(2n)。

因此，我们上面推导中存在的最大问题就是没有把各种情况的概率都考虑进去。如果我们把每种情况发生的概率也考虑进去，那平均情况时间复杂度的计算就变成了下面这样：

在引入概率论之后，我们的分析结果仍然是O(n)，但是这才是正确的推导过程。这个值就是概率论中的加权平均值，也叫期望值，所以平均情况时间复杂度也叫做加权平均时间复杂度或者期望时间复杂度。

实际上，大多数情况下，我们并不需要区分最好、最坏和平均情况时间复杂度三种情况，很多时候，就像我们上一篇文章中举过的例子一样，我们使用一种复杂度就可以满足需求了。只有同一块代码，在不同的情况下，时间复杂度具有量级的差距的时候，我们才会使用三种复杂度来进行区分。

均摊时间复杂度

目前为止，我们已经介绍了算法复杂度分析的绝大部分内容，下面我们来讨论一个比较特殊的概念，均摊时间复杂度，以及它对应的分析方法，摊还分析。

均摊时间复杂度，听起来感觉和平均情况时间复杂度有点像，而这两者也确实比较容易混淆。上文提到过，大部分情况下我们不用区分最好、最坏和平均三种复杂度，平均情况时间复杂度只在某些特殊情况下才会用到，而均摊时间复杂度的应用场景则更加特殊、更加有限。

我们来看下面的例子，下面的代码是非常规写法，这里只是为了方便举例：

// 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 值放到数组的第一个位置，然后再将新的数据插入。但如果数组一开始就有空闲空间，则直接将数据插入数组。

那这段代码的时间复杂度是多少呢？我们先试着用上文中介绍的最好、最坏、平均情况三种时间复杂度来分析一下。

最理想的情况下，数组中有空闲空间，这个时候只需要把数据插入到数组下标为count的位置就可以了，所有最好情况时间复杂度就是O(1)；最坏的情况下，数组中没有空闲空间了，我们需要先做一次数组遍历求和，然后再将数据插入，所以最坏情况时间复杂度就是O(n)。

那平均情况时间复杂度是多少呢？我们还是通过前面介绍的概率论的方法进行分析。假设数组的长度是n，根据数据插入的位置的不同，我们可以分为n中情况，每种情况的时间复杂度是O(1)。除此之外，还有一种“额外”的情况，就是在数组没有空闲位置的时候插入一个数据，这个时候的时间复杂度是O(n)。也就是说，一共有n+1中情况，而这n+1中情况发生的概率是一样的，都是1/(n+1)，如此，我们不难计算出上面代码的平均情况时间复杂度就是O(1)。

但是对上面代码的时间复杂度分析我们有必要这么复杂吗？我们来仔细分析一下上面代码的特征：

• 如果不出现数组中没有空闲位置这个特殊情况，代码的时间复杂度永远是O(1)，没有出现量级的差异；
• 数组中没有空闲位置这个特殊情况的出现具有一定的周期性，是在一个O(n)操作之后，紧跟着出现n-1个O(1)的插入操作，循环往复。

所以，针对这样一个特殊场景的复杂度分析，我们并不需要像之前讲平均复杂度分析方法那样，找出所有的输入情况及相应的发生概率，然后再计算加权平均值。我们引入了一种更加简单的分析方法：摊还分析法，而通过摊还分析得到的时间复杂度我们称为均摊时间复杂度。

那摊还分析法是如何对一段代码的时间复杂度进行分析的呢？我们继续沿用上文中数据插入的例子。

既然上面的插入操作是在一个O(n)操作之后，紧跟着出现n-1个O(1)的插入操作，循环往复。那么我们是不是可以把那个O(n)操作均摊到接下来的n-1次O(1)操作上，也就是我们把这个O(n)操作平均分成n分，给接下来的n-1个O(1)操作各一份，它自己本身留一份，均摊下来之后，原来的n-1次O(1)操作的复杂度变成了O(2)，简化之后就是O(1)；而原来的O(n)复杂度的操作变成了O(1)，根据时间复杂度的加法规则，这一组连续的操作的均摊时间复杂度就是 O(1)。这就是均摊分析的大致思路。

均摊时间复杂度和摊还分析的应用场景都是比较特殊的，大多数情况我们不会使用，只有在以下场景中我们才会考虑使用摊还分析法来得到算法的均摊时间复杂度：

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

其实，均摊时间复杂度就是一种特殊的平均情况时间复杂度，我们没有必要花费太大的力气去区分它们，我们这里介绍均摊时间复杂度主要是为了介绍它对应的摊还分析法，当我们在遇到可以使用摊还分析的场景的时候，可以加速我们的分析。

常见的时间复杂度

到现在，我们对于算法时间复杂度分析的介绍已经比较全面了，下面我们来介绍一下我们在编码的时候都会遇到哪些形式的时间复杂度，以及它们之间的优劣，对于一个算法，我们不光要有基本的是非观，还要知道它的好坏程度。

虽然代码千差万别，但是常见的复杂度量级并不多，这里我们稍微总结一下，下面列出的复杂度表示中量级是按从小到大排列的：

• 常量阶 O(1)

• 对数阶 O(logn)

• 线性阶 O(n)

• 线性对数阶 O(nlogn)

• 平方阶 O(n²)、立方阶 O(n³)...k次方阶 O(n^k)

  需要注意的是，这里的k次方阶中的k必须是一个常量，是与输入数据无关的

• 指数阶 O(2ⁿ)

• 阶乘阶 O(n!)

对于上面罗列的复杂度量级，我们可以粗略地分为两类，多项式量级和非多项式量级。其中，非多项式量级只有两个：O(2ⁿ)和O(n!)。我们把时间复杂度为非多项式量级的算法问题叫做NP(Non-Deterministic Polynomial，非确定多项式)问题。

当数据规模n越来越大的时候，非多项式量级算法的执行时间会急剧增加，所以，非确定多项式时间复杂度的算法是非常低效的，我们在编码的时候遇到这样复杂度的代码也往往会想办法优化掉，因此，关于NP时间复杂度这里就不展开讲了。我们主要关注几种常见的多项式时间复杂度。

O(1)

首先你必须明确一个概念，O(1) 只是常量级时间复杂度的一种表示方法，并不是指只执行了一行代码。比如:

int i = 8;
int j = 6;
int sum = i + j;
复制代码

即便有 3 行，它的时间复杂度也是 O(1），而不是 O(3)。

其实，只要是代码的执行时间不随n的增大而增长，这样的代码的时间复杂度我们都记为O(1)。一般情况下，只要算法中不存在循环语句、递归语句，即使有成千上万行的代码，其时间复杂度也是Ο(1)。同时，固定次数循环的时间复杂度也是O(1)。

O(logn)、O(nlogn)

对数阶时间复杂度非常常见，同时也是最难分析的一种时间复杂度。我们来看下面的代码：

i=1;
while (i <= n)  {
    i = i * 2;
}
复制代码

根据我们前面讲的复杂度分析方法，第三行代码是循环执行次数最多的。所以，我们只要能计算出这行代码被执行了多少次，就能知道整段代码的时间复杂度。从代码中可以看出，变量 i 的值从 1 开始取，每循环一次就乘以 2。当大于 n 时，循环结束。还记得我们高中学过的等比数列吗？实际上，变量 i 的取值就是一个等比数列。如果我把它一个一个列出来，就应该是这个样子的：

所以，我们只要知道 x 值是多少，就知道这行代码执行的次数了。x=log₂n，所以，这段代码的时间复杂度就是 O(log₂n)。

下面，我们把上面的代码稍作修改：

i=1;
while (i <= n)  {
    i = i * 3;
}
复制代码

根据刚刚的思路，我们不难算出这段代码的时间复杂度就是O(log₃n)，而我们知道，对数之间是可以互相转换的，log₃n 就等于 log₃2 × log₂n，其中 log₃2 是一个常量。基于我们前面的一个理论：在采用大 O 标记复杂度的时候，可以忽略系数，所以，O(log2n) 就等于 O(log3n)。

因此，在对数阶时间复杂度的表示方法里，我们忽略对数的“底”，统一表示为 O(logn)。

O(m+n)、O(m*n)

我们再来讲一种跟前面都不一样的时间复杂度，代码的复杂度由两个数据的规模来决定，看下面的代码：

int cal(int m, int n) {
    int sum_1 = 0;
    int i = 1;
    for (; i < m; ++i) {
        sum_1 = sum_1 + i;
    }

    int sum_2 = 0;
    int j = 1;
    for (; j < n; ++j) {
        sum_2 = sum_2 + j;
    }

    return sum_1 + sum_2;
}
复制代码

从代码中可以看出，m 和 n 是表示两个数据规模。我们无法事先评估 m 和 n 谁的量级大，所以我们在表示复杂度的时候，就不能简单地利用加法法则，省略掉其中一个。所以，上面代码的时间复杂度就是 O(m+n)。

针对这种情况，原来的加法法则就不正确了，我们需要将加法规则改为：T1(m) + T2(n) = O(f(m) + g(n))。但是乘法法则继续有效：T1(m)×T2(n) = O(f(m)×f(n))。

总结

目前为止，我们上篇文章介绍了渐进时间复杂度分析的基本方法，包括只考虑主要矛盾、加法法则和乘法法则，知道了数据规模对算法执行效率的影响，而这篇文章我们又介绍了不同情况下的时间复杂度，包括最好情况时间复杂度（best case time complexity）、最坏情况时间复杂度（worst case time complexity）、平均情况时间复杂度（average case time complexity）、均摊时间复杂度（amortized time complexity），知道了如何针对数据的不同情况对算法进行分析，同时我们也介绍了常见的几种时间复杂度，相信，在之后我们遇到的绝大多数的代码我们都可以对其进行复杂度的分析了。

本人深知自己技术水平和表达能力有限，文章中一定存在不足和错误，欢迎与我进行交流(laomst@163.com)，跟我一起交流，修改文中的不足和错误，感谢您的阅读。