数据结构与算法 --- 复杂度分析专题（二）

Niuery Diary

发布于 2023-10-22 16:54:36

2430

发布于 2023-10-22 16:54:36

文章被收录于专栏：Niuery的技术日记

引言

在上一篇复杂度分析专题（一）中，学习了复杂度的大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#代码：

//假设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)

。

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

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(n)

」

平均时间复杂度

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

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

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

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

E(X)=\sum_{i}x_i × P(x_i)

「其中，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中情况。

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

1×\frac{1}{2n}+2×\frac{1}{2n}+3×\frac{1}{2n}+...+n×\frac{1}{2n}+n×\frac{1}{2}=\frac{3n+1}{4}

所以最后计算到期望值为

\frac{3n+1}{4}

，根据大O复杂度表示法表示，去掉系数和常量，最后的得到平均时间复杂度为

O(n)

。

需要注意的是，只有当同一段代码在不通过情况下性能表现不同，并且时间复杂度有量级的差别时，才会使用这三种不同的复杂度来表示。

均摊时间复杂度

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

有如下代码：

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，然后将新数据插入。

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