最好、最坏与平均情况

学习目标

本节学习复杂度分析中的三种常见情况：最好情况、最坏情况和平均情况。

同一个算法在不同输入下，运行步骤可能不同。理解这些情况，有助于我们更准确地描述算法表现，而不是只给出一个模糊结论。

顺序查找的三种情况

仍然以顺序查找为例。它从第一个元素开始逐个检查，直到找到目标值。

int findIndex(const vector<int>& numbers, int target) {
    for (int i = 0; i < numbers.size(); i++) {
        if (numbers[i] == target) {
            return i;
        }
    }

    return -1;
}

int findIndex(int[] numbers, int target) {
    for (int i = 0; i < numbers.length; i++) {
        if (numbers[i] == target) {
            return i;
        }
    }

    return -1;
}

def find_index(numbers, target):
    for index, number in enumerate(numbers):
        if number == target:
            return index

    return -1

int FindIndex(int[] numbers, int target)
{
    for (int i = 0; i < numbers.Length; i++)
    {
        if (numbers[i] == target)
        {
            return i;
        }
    }

    return -1;
}

如果目标值就在第一个位置，只需要比较 1 次。这是最好情况，复杂度可以看作 $O(1)$ 。

如果目标值在最后一个位置，或者根本不存在，就需要比较 $n$ 次。这是最坏情况，复杂度是 $O(n)$ 。

如果目标值可能均匀出现在任意位置，平均大约需要检查一半元素。虽然是大约 $n / 2$ 次，但大 O 会忽略常数，所以平均情况通常仍然记为 $O(n)$ 。

为什么常用最坏情况

在很多学习和面试场景中，我们更常讨论最坏情况复杂度。

原因是最坏情况给出了一个比较稳妥的上限。它告诉我们：无论输入如何糟糕，这个算法最多会增长到什么级别。

例如，顺序查找最坏是 $O(n)$ 。这意味着只要输入规模是 $n$ ，它最多可能需要检查全部元素。这个结论比“有时候很快”更适合用来评估稳定性。

平均情况不一定容易分析

平均情况听起来更接近真实使用，但它通常依赖输入分布。

例如，如果你总是查找列表开头附近的元素，平均表现可能很好；如果目标值经常不存在，平均表现就接近最坏情况。

要严谨分析平均情况，往往需要知道数据出现的概率分布。对于初学阶段，可以先重点掌握最好情况和最坏情况，再逐渐理解平均情况。

不同情况的表达方式

描述算法复杂度时，最好明确说明你说的是哪一种情况。

例如：

顺序查找最好情况是 $O(1)$ 。
顺序查找最坏情况是 $O(n)$ 。
在目标位置均匀分布的假设下，顺序查找平均情况是 $O(n)$ 。

这样表达比只说“顺序查找是 $O(n)$ ”更加准确。不过在没有特别说明时，很多教材和讨论默认指最坏情况。

本节小结

同一个算法在不同输入下可能有不同复杂度表现。

最好情况表示最顺利输入下的成本，最坏情况表示最不利输入下的成本，平均情况表示在某种输入分布假设下的期望成本。学习阶段要特别重视最坏情况，因为它能帮助我们判断算法表现的稳定上限。