引言

在上一篇复杂度分析专题（一）中，学习了复杂度的大O表示法和一些常见复杂度（$O(1)$、$O(n)$、$O(logn)$、$O(n^2)$等等）的分析方法，下面介绍4个更加细分的复杂度概念：

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

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

现有如下C#代码：

csharp
//假设arr 是无序的，无重复的数组
public int FindIndex(int[] arr,int param)
{
    int pos = -1;
    int n = arr.Length;
    for (int i = 0; i < n; i++)
    {
        if (arr[i] == param) pos = i;
    }

    return pos;
}

代码功能是在一个无序数组中，找出param在数组中的位置，若没有找到，则返回-1。

按照上一篇中介绍的复杂度计算方法，该方法的复杂度为$O(n)$。

但是在数组中查找一个元素时，不一定会全部遍历一遍，又可能提前找到，遍历就结束了，所以可以像这样优化一下代码：

csharp
public int FindIndex(int[] arr,int param)
{
    int pos = -1;
    int n = arr.Length;
    for (int i = 0; i < n; i++)
    {
        if (arr[i] == param) 
        {
            pos = i;
            break;
        }   
    }

    return pos;
}

那这个时候算法复杂度就不再是$O(n)$了

• 若数组中的第一个元素正好是要查询的元素，那么此时的时间复杂度就是$O(1)$。
• 若数组中没有相匹配的元素，就需要将整个数组遍历一遍，那么此时的时间复杂度就是$O(n)$。

所以针对上述第一种情况，称之为最好情况时间复杂度$O(1)$,针对上述第一种情况，称之为最坏情况时间复杂度$O(1)$

平均时间复杂度

最好时间复杂度和最坏时间复杂度对应的都是极端情况下的复杂度，发生概率低。所以就引入了平均情况下的复杂度，平均时间复杂度。

平均时间复杂度指的是代码被执行无数次，对应的时间复杂度的平均值。

整个平均值实际上指的是概率论中的加权平均值，也称期望值。

期望值是概率论和统计学中一个非常重要的概念，通常指随机变量的平均值。在离散情况下，期望值的计算公式为：

其中，X是一个随机变量，$x_i$是X可以取到的每个值，$P(x_i)$是X取到$x_i$的概率。

依旧借助上文中第二段代码的例子，要查找元素param在数组中的位置，有两种情况，在数组内或者不在数组内，两种情况出现的概率都是$\frac{1}{2}$，另外，要查找的数据出现在0到n-1的位置的概率是一样的，都是$\frac{1}{n}$，因此根据概率乘法法则，要查找的数据出现在0到n-1中任意位置的概率是$\frac{1}{2n}$，总共是n+1中情况。

所以上文中例子的时间复杂度的计算过程如下：

所以最后计算到期望值为$\frac{3n+1}{4}$，根据大O复杂度表示法表示，去掉系数和常量，最后的得到平均时间复杂度为$O(n)$。

均摊时间复杂度

下面介绍一平均时间复杂度的特殊情况：均摊时间复杂度，使用平摊分析法。

有如下代码：

csharp
private int[] arr = new int[n];
private int count = 0;

public void Insert(int value)
{
    if (count == arr.Length)
    {
        int sum = 0;
        for (int i = 0; i < arr.Length; i++)
        {
            sum += arr[i];
        }
        count = 0;
    }
    arr[count] = value;
    count++;
}

上述代码实现了向数组中插入数据的功能，如果数组中有未占用空间，就直接将数据插入到数组中，当数组满了之后count == arr.Length，遍历数组求和，同时清空数组count = 0，然后将新数据插入。

分析一下它的时间复杂度：

• 最好情况，数组中有未占用空间，只需要将数据插入到数组下标为count的位置，此时为最好时间复杂度$O(1)$。
• 最坏情况，数据中全满，先遍历求和，再插入数据，此时为最坏时间复杂度$O(n)$。
• 平均情况，假设数组长度是n，
  • 当有未占用空间时，分别能插入下标为0到n-1的位置，共有n中情况。
  • 当全满时，是一种情况。
  • 这n+1种情况的概率是一样为$\frac{1}{n+1}$
  所以根据期望值的计算方法，转化为大O表示法得到的平均时间复杂度如下

但是仔细观察Insert方法，它其实在大部分情况下时间复杂度都为$O(1)$，只有极个别情况，时间复杂度才为$O(n)$，且两者在出现的频率是有规律的，两者有一定的前后时序关系，在一个$O(n)$时间复杂度的插入之后，紧跟着会有n-1个$O(1)$时间复杂度的插入操作，不断循环。

针对这样一个特殊场景的平均时间复杂度分析，可以使用一种更加简单的分析方法：平摊分析法，通过平摊分析法得到的时间复杂度，命名为：均摊时间复杂度。

具体怎么分析均摊时间复杂度呢？

我们观察到，每一次$O(n)$时间复杂度的插入操作都会跟着n-1个$O(1)$时间复杂度的插入操作，因此，可以将耗时多的那次操作的耗时均摊到接下来的n-1次的耗时少的操作上，那么均摊下来，这一组的连续插入操作的均摊时间复杂度就变为了$O(1)$。

参考资料

[1] 数据结构与算法之美 / 王争 著. --北京：人民邮电出版社，2021.6