上篇介绍了 大 O 表示法以及常见的复杂度分析案例，这篇介绍四个复杂度分析方面的知识点：

• 最好情况时间复杂度 (best case time complexity)
• 最坏情况时间复杂度 (worst case time complexity)
• 平均情况时间复杂度 (average case time complexity)
• 均摊时间复杂度 (amortized time complexity)

这四个知识点搭配上章的 大O表示法，基本上囊括了复杂度分析需要的知识。

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

上节的例子比较简单，下面是一个比较复杂的，可以先用之前的知识分析一下下面这段代码的时间复杂度：

		/**
     * 分析：数据规模是不确定的所以不能忽略，而是要相加 首先要循环 n 次，所以 O(n) 
     * 另外循环进行判断 pos == x 最好情况是第一次就找到，最坏是最后找到，也就是又循环了 n 次
     * O(1) ~ O(n) ，按最坏来 O(n+n) O(2n) 忽略常数 O(n)
     */
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;
}

作者的解析：这段代码要实现的功能是在无序的数组中查找变量 x 的出现位置，如果没有找到就返回 -1。所以这段代码的复杂度是 O(n)，n 代表数组长度。

【这里我的结论虽然没错，但是过程有问题，问题出在 if 判断上，我好像想复杂了。】

同时，我们查找数据并不一定要完整的遍历一遍，如果找到之后应该结束循环，所以上面这段代码不够高效，优化之后的代码如下：

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)（最好情况），如果最后一个才是，代表将整个数组遍历了一遍，所以是 O(n)）（最差情况）。不同情况下，这段代码的复杂度不同。

为了表示代码在不同情况下的不同复杂度，引入了下面三个概念：

• 最好情况时间复杂度：最理想情况下执行代码的时间复杂度，对应上面的查找元素位于数组第一个的 O(1)
• 最坏情况时间复杂度：最糟糕情况下执行代码的复杂度，对应上面的遍历整个数组的 O(n)
• 平均情况时间复杂度

平均情况时间复杂度

最好情况和最坏情况的复杂度对应的是极端情况下代码的复杂度，发生概率不大。为了更好地表示平均情况下的复杂度，需要引入另一个概念：

• 平均情况时间复杂度。

用上面的例子说明平均情况时间复杂度的分析方法：

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

时间复杂度的 大O 标记法中，可以 忽略 系数、低阶、常量，所以将上面的公式简化，得到的平均复杂度就是 O(n)。

这个结论虽然正确，但是计算过程有一些问题。因为刚才讲到的 n+1 种情况的出现概率并不一样。（这里会涉及到简单的概率论知识）

要查找的变量 x ，要么在数组里，要么不再。这两种情况对应的概率统计起来很麻烦，为了方便理解，这里假设在与不在概率都是 1/2。另外要查找数据出现在 0 ~ n-1 这 n 个位置上的概率也一样 —— 1/n。

所以根据概率乘法法则：要查找的数据出现在 0 ~ n-1 中任意位置的概率是 1 / (2n)。【也就是在数组中的概率 * 数组中每个位置的出现概率： 1/2 * 1/n = 1/2n】

之前推导过程最大的问题是，没有将各种情况的发生概率考虑进去。如果将各个情况的发生概率考虑进去，则**平均复杂度**的计算过程变成了下面这样：

这个值就是概率论中的加权平均值，也叫期望值。所以平均时间复杂度的全程是：加权平均时间复杂度或期望时间复杂度。

引入概率之后，上面那段代码的加权平均值为 (3n+1) / 4 ，去掉常数之后，复杂度仍然为 O(n)。

实际上，在大多数情况下，并不需要区分最好、最坏、平均情况三种时间复杂度。很多时候使用一个时间复杂度就可以满足需求了，只有同一块代码在不同情况下时间复杂度有量级差距时，才会使用这三种复杂度进行区分。

【这里的关键点：

• 同一代码
• 不同情况
• 时间复杂度有量级差距（个人认为最重要）

上面的例子最好最坏和平均虽然具体值不同，但是在省略系数低阶和常量之后的时间复杂度都是 O(n)】

均摊时间复杂度

均摊时间复杂度是一个更加高级的概念，下面要介绍的是对应的分析方法 —— 摊还分析（平摊分析）。

均摊时间复杂度看起来和平均时间复杂度有点像，这两个概念确实很容易混淆。大部分情况下也并不用区分最好、最坏、平均三种情况。并且平均只有在某些特殊情况下才会用到，均摊复杂度比平均复杂度更特殊，应用场景更有限。

下面是一个为了理解概念编写的例子，真实情况没有人会这样写：

// array 代表一个长度为 n 的数组， 方法中的 array.lenght 就是数据规模 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;
}

上面的代码实现了往数组中插入数据的功能，当数组已满之后 也就是当 count == array.length 条件成立，遍历数组求和，并清空数组，求和之后将数组之和放到数组中的第一个位置，然后将新的数组插入。

如果数组一开始就有空闲空间，则直接将数据插入数组。

使用之前的三种时间复杂度来分析上面的代码：

• 最理想情况：数组中有空闲空间，只需要将数据插入到下标为 count 的位置即可，此时的时间复杂度是常量 O(1)

• 最坏情况：数组已满，需要遍历求和之后再插入数据，复杂度为 O(n)

• 平均复杂度：O(1) ，还是用之前的概率论方法来分析。

  • 假设数组长度为 n，根据插入位置不同，可以分为 n 种情况，每种情况的时间复杂度是 O(1)。
  • 还有一种额外情况，在数组没有空闲空间时插入一个数组，这个时间复杂度是 O(n)
  • 这 n + 1 种情况发生的概率相同 --> 1 / (n+1)
  • 根据平均加权求得：最终平均复杂度：O(1)

  

上面的最好最坏理解起来都很简单，但是平均复杂度实际不需要像上面分析的那么复杂度，并不需要引入概率论知识。对比上面的 insert() 和 find() 两个例子，这两者有很大的差别：

• find 函数在极端情况下，复杂度才是O(1)，但是 insert() 在大部分情况下 复杂度都是 O(1)
• insert O(1) 时间复杂度的插入 和 O(n) 时间复杂度的插入出现的频率很有规律，且存在前后时序关系，一般是 1 个 O(n) 插入之后紧跟着 n-1 个 O(1)，循环往复。

所以针对这种有规律且存在前后时序的特殊情况，不需要找出所有输入情况以及对应的发生概率然后再加权，这里引入了一种更简单的分析方法：摊还分析法，通过这种方法得到的时间复杂度被称为 —— 均摊时间复杂度。

下面是摊还分析法的具体使用：

上面的例子中，每一次 O(n) 插入操作之后都会伴随 n-1 次 O(1) 插入操作，所以把耗时多的操作均摊到之后 n-1 次耗时少的操作上，均摊下来，这一组操作的时间复杂度就是 O(1)，这就是均摊分析的大致思路。【也就是将大部分情况的时间复杂度作为整体的复杂度】

均摊复杂度以及摊还分析很特殊，了解有这么个事儿就行了，下面是特征：

• 连续操作存在规律
• 大部分情况时间复杂度都很低，个别情况比较高
• 操作之间存在连贯时序关系

一般均摊时间复杂度等于最好情况时间复杂度。

同时我们没有必要花费大量精力区分平均时间复杂度和均摊时间复杂度，作者认为均摊时间复杂度是平均时间复杂度的一种，我们的重点是掌握分析方法 —— 摊还分析，不需要纠结复杂度名称与模式。

内容小结

这节介绍了一种情况：代码在不同输入的情况下，复杂度量级不一样的情况，从而引出了最好最坏和平均时间复杂度。

加上之前的 大 O 分析法，就可以比较全面的分析代码的复杂度了。

课后思考

重要留言

Q.E.D.