数据结构与算法 / 系统课时

最好、最坏与平均情况

最好、最坏与平均情况

学习目标

  • 理解最好情况、最坏情况和平均情况的定义。
  • 能分析线性查找在不同目标位置下的比较次数。
  • 理解平均情况依赖输入概率分布。
  • 建立工程性能视角,区分平均延迟、最坏延迟和尾部延迟。
  • 输入差异
    • 目标位置
    • 是否命中
    • 数据顺序
    • 重复值
    • 概率分布
  • 性能情况
    • 最好情况
    • 最坏情况
    • 平均情况
    • 摊还情况
  • 工程指标
    • 平均耗时
    • 最大耗时
    • 中位数
    • P95
    • P99
  • 分析原则
    • 说明输入条件
    • 说明概率假设
    • 不用单次运行下结论
    • 关注稳定性与上界

问题背景或应用场景

线性查找从第一个元素开始逐个比较。如果目标值正好位于第一个位置,只需要比较一次。如果目标值位于最后一个位置,需要比较全部元素。如果目标值不存在,同样需要检查全部元素。因此,同一个算法在不同输入下,执行次数可能不同。

在工程系统中,不同业务对性能情况的关注点也不同:

  • 实时支付接口通常关注最坏延迟和尾部延迟。
  • 离线报表任务更关注总耗时和平均吞吐量。
  • 搜索推荐可能关注典型用户请求。
  • 安全系统可能必须保证最坏情况下仍能及时响应。
  • 批量导入需要评估大规模输入时的稳定性。

如果只根据一次运行结果评价算法,很容易得出错误结论。

核心原理

1. 最好情况

最好情况表示在最有利输入下,算法执行的最少操作次数。对于线性查找:

  • 目标位于第一个位置。
  • 只比较一次。
  • 最好时间复杂度为 O(1)。

2. 最坏情况

最坏情况表示在最不利输入下,算法执行的最多操作次数。对于线性查找:

  • 目标位于最后一个位置。
  • 或目标不存在。
  • 需要比较 n 次。
  • 最坏时间复杂度为 O(n)。

最坏情况非常重要,因为它描述性能上界。

3. 平均情况

平均情况描述某种输入概率分布下的期望操作次数。假设:

  • 列表长度为 n。
  • 目标一定存在。
  • 目标等概率出现在每个位置。

比较次数分别为:

text
1 2 3 ... n

平均比较次数为:

text
(1 + 2 + 3 + ... + n) / n

利用等差数列求和公式:

text
1 + 2 + 3 + ... + n = n(n + 1) / 2

得到:

text
平均比较次数 = (n + 1) / 2

忽略常数和低阶项后,平均复杂度仍为 O(n)。

4. 平均情况必须说明概率假设

如果目标更可能出现在前面,平均比较次数会降低。如果目标经常不存在,平均比较次数会接近 n。因此,没有输入分布假设,就不能严谨地计算平均情况。

5. 平均耗时不能代替最坏耗时

假设某接口大多数请求耗时 10 毫秒,少量请求耗时 2 秒。平均值可能仍然看起来不高,但用户会感受到明显卡顿。工程中常使用以下指标:

  • 平均值:所有耗时总和除以请求数量。
  • 中位数:一半请求低于该值。
  • P95:95% 请求低于该值。
  • P99:99% 请求低于该值。
  • 最大值:观测到的最大耗时。

算法课程中的最好、最坏和平均情况,为理解这些工程指标提供了基础。

6. 分支条件会导致不同路径

算法中只要存在提前返回、条件分支或不同循环终止条件,就可能出现不同执行情况。分析时应问:

  • 什么输入会最快结束。
  • 什么输入会执行最多步骤。
  • 常见输入如何分布。
  • 系统是否能够接受最坏情况。

基础用法

线性查找的情况分析

列表:

text
10 20 30 40 50

查找 10:

text
比较 1 次
最好情况

查找 50:

text
比较 5 次
最坏命中情况

查找 99:

text
比较 5 次
最坏未命中情况

如果目标等概率出现在五个位置,平均比较次数为:

text
(1 + 2 + 3 + 4 + 5) / 5 = 3

二分查找的情况分析

二分查找的最好情况是目标正好位于第一次检查的中间位置,复杂度为 O(1)。

最坏情况下,每次都需要继续缩小范围,复杂度为 O(log n)。这说明同一个算法也可以同时拥有不同情况复杂度。

完整可运行示例

python
from collections.abc import Sequence

def linear_search_with_count(
    values: Sequence[int],
    target: int,
) -> tuple[int, int]:
    comparisons = 0

    for index, value in enumerate(values):
        comparisons += 1

        if value == target:
            return index, comparisons

    return -1, comparisons

def average_successful_count(values: Sequence[int]) -> float:
    if not values:
        raise ValueError("values cannot be empty")

    total_comparisons = 0

    for target in values:
        _, comparisons = linear_search_with_count(values, target)
        total_comparisons += comparisons

    return total_comparisons / len(values)

def average_count_with_queries(
    values: Sequence[int],
    queries: Sequence[int],
) -> float:
    if not queries:
        raise ValueError("queries cannot be empty")

    total_comparisons = 0

    for target in queries:
        _, comparisons = linear_search_with_count(values, target)
        total_comparisons += comparisons

    return total_comparisons / len(queries)

def main() -> None:
    values = [10, 20, 30, 40, 50]

    best_index, best_count = linear_search_with_count(values, 10)
    last_index, last_count = linear_search_with_count(values, 50)
    missing_index, missing_count = linear_search_with_count(values, 99)

    successful_average = average_successful_count(values)

    front_weighted_queries = [10, 10, 10, 20, 30]
    missing_weighted_queries = [10, 99, 99, 99, 99]

    front_average = average_count_with_queries(
        values,
        front_weighted_queries,
    )
    missing_average = average_count_with_queries(
        values,
        missing_weighted_queries,
    )

    print(f"best: index={best_index}, comparisons={best_count}")
    print(f"last: index={last_index}, comparisons={last_count}")
    print(
        f"missing: index={missing_index}, "
        f"comparisons={missing_count}"
    )
    print(f"equal successful average: {successful_average:.1f}")
    print(f"front weighted average: {front_average:.1f}")
    print(f"missing weighted average: {missing_average:.1f}")

if __name__ == "__main__":
    main()

运行命令:

bash
python lesson_01_05.py

预期输出

text
best: index=0, comparisons=1
last: index=4, comparisons=5
missing: index=-1, comparisons=5
equal successful average: 3.0
front weighted average: 1.6
missing weighted average: 4.2

输出分析

等概率成功查询:

text
10 20 30 40 50

比较次数分别为:

text
1 2 3 4 5

平均值为 3.0。前部高频查询:

text
10 10 10 20 30

比较次数为:

text
1 1 1 2 3

平均值为 1.6。未命中高频查询:

text
10 99 99 99 99

比较次数为:

text
1 5 5 5 5

平均值为 4.2。这说明平均情况由真实查询分布决定。

Tips

  • 最好情况通常不能代表稳定性能。
  • 最坏情况适合评估性能上界。
  • 平均情况必须说明输入分布。
  • 目标不存在也属于重要输入情况。
  • 提前返回会产生不同执行路径。
  • 相同大 O 复杂度下,平均比较次数可能不同。
  • 工程系统还需要关注 P95 和 P99。
  • 对强实时系统,应优先保证最坏情况可控。
  • 对批处理系统,可以更关注总体吞吐量。
  • 测试平均性能时,需要使用代表真实业务的数据分布。
  • 不要使用过于理想的随机数据替代真实负载。
  • 复杂度分析与生产监控应结合使用。

常见错误

错误一:只报告最好情况

目标位于首位时很快,不代表其他输入也快。

错误二:把平均情况理解为最好与最坏的简单平均

平均情况需要对所有可能输入及其概率进行加权。

错误三:不说明目标是否存在

目标不存在时,线性查找通常需要扫描全部元素。

错误四:默认所有输入等概率

真实业务中,热门数据和冷门数据的访问概率通常不同。

错误五:用一次运行结果代表算法性能

单次运行可能受到系统负载、缓存和偶然因素影响。

错误六:只看平均值

平均值可能掩盖少量非常慢的请求。

错误七:把复杂度相同理解为性能完全相同

两个 O(n) 算法可能有不同常数开销、缓存行为和提前退出概率。

本课练习

  1. 计算长度为 10 的列表中,目标等概率存在时的平均比较次数。
  2. 分析目标不存在概率为 50% 时,线性查找平均比较次数如何变化。
  3. 修改示例,使查询更集中在列表尾部。
  4. 记录不同查询分布下的平均比较次数。
  5. 分析二分查找的最好和最坏情况。
  6. 分析冒泡排序在已排序输入和逆序输入下的差异。
  7. 思考支付接口为什么更关注最坏延迟和 P99。
  8. 思考离线统计为什么更关注总吞吐量。
  9. 设计一个查询分布,其中线性查找平均只需要接近一次比较。
  10. 设计一个查询分布,其中线性查找平均接近 n 次比较。
按自己的节奏,确认真正理解。

目录与阅读设置

阅读设置

17

记录一个想法

最好、最坏与平均情况

0 / 10000 · 笔记保存到账号。未提交的修改会在关闭、离开或刷新后丢失。

登录哪都通