数据结构与算法 / 系统课时
最好、最坏与平均情况
最好、最坏与平均情况
学习目标
- 理解最好情况、最坏情况和平均情况的定义。
- 能分析线性查找在不同目标位置下的比较次数。
- 理解平均情况依赖输入概率分布。
- 建立工程性能视角,区分平均延迟、最坏延迟和尾部延迟。
- 输入差异
- 目标位置
- 是否命中
- 数据顺序
- 重复值
- 概率分布
- 性能情况
- 最好情况
- 最坏情况
- 平均情况
- 摊还情况
- 工程指标
- 平均耗时
- 最大耗时
- 中位数
- P95
- P99
- 分析原则
- 说明输入条件
- 说明概率假设
- 不用单次运行下结论
- 关注稳定性与上界
问题背景或应用场景
线性查找从第一个元素开始逐个比较。如果目标值正好位于第一个位置,只需要比较一次。如果目标值位于最后一个位置,需要比较全部元素。如果目标值不存在,同样需要检查全部元素。因此,同一个算法在不同输入下,执行次数可能不同。
在工程系统中,不同业务对性能情况的关注点也不同:
- 实时支付接口通常关注最坏延迟和尾部延迟。
- 离线报表任务更关注总耗时和平均吞吐量。
- 搜索推荐可能关注典型用户请求。
- 安全系统可能必须保证最坏情况下仍能及时响应。
- 批量导入需要评估大规模输入时的稳定性。
如果只根据一次运行结果评价算法,很容易得出错误结论。
核心原理
1. 最好情况
最好情况表示在最有利输入下,算法执行的最少操作次数。对于线性查找:
- 目标位于第一个位置。
- 只比较一次。
- 最好时间复杂度为 O(1)。
2. 最坏情况
最坏情况表示在最不利输入下,算法执行的最多操作次数。对于线性查找:
- 目标位于最后一个位置。
- 或目标不存在。
- 需要比较 n 次。
- 最坏时间复杂度为 O(n)。
最坏情况非常重要,因为它描述性能上界。
3. 平均情况
平均情况描述某种输入概率分布下的期望操作次数。假设:
- 列表长度为 n。
- 目标一定存在。
- 目标等概率出现在每个位置。
比较次数分别为:
1 2 3 ... n平均比较次数为:
(1 + 2 + 3 + ... + n) / n利用等差数列求和公式:
1 + 2 + 3 + ... + n = n(n + 1) / 2得到:
平均比较次数 = (n + 1) / 2忽略常数和低阶项后,平均复杂度仍为 O(n)。
4. 平均情况必须说明概率假设
如果目标更可能出现在前面,平均比较次数会降低。如果目标经常不存在,平均比较次数会接近 n。因此,没有输入分布假设,就不能严谨地计算平均情况。
5. 平均耗时不能代替最坏耗时
假设某接口大多数请求耗时 10 毫秒,少量请求耗时 2 秒。平均值可能仍然看起来不高,但用户会感受到明显卡顿。工程中常使用以下指标:
- 平均值:所有耗时总和除以请求数量。
- 中位数:一半请求低于该值。
- P95:95% 请求低于该值。
- P99:99% 请求低于该值。
- 最大值:观测到的最大耗时。
算法课程中的最好、最坏和平均情况,为理解这些工程指标提供了基础。
6. 分支条件会导致不同路径
算法中只要存在提前返回、条件分支或不同循环终止条件,就可能出现不同执行情况。分析时应问:
- 什么输入会最快结束。
- 什么输入会执行最多步骤。
- 常见输入如何分布。
- 系统是否能够接受最坏情况。
基础用法
线性查找的情况分析
列表:
10 20 30 40 50查找 10:
比较 1 次
最好情况查找 50:
比较 5 次
最坏命中情况查找 99:
比较 5 次
最坏未命中情况如果目标等概率出现在五个位置,平均比较次数为:
(1 + 2 + 3 + 4 + 5) / 5 = 3二分查找的情况分析
二分查找的最好情况是目标正好位于第一次检查的中间位置,复杂度为 O(1)。
最坏情况下,每次都需要继续缩小范围,复杂度为 O(log n)。这说明同一个算法也可以同时拥有不同情况复杂度。
完整可运行示例
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()运行命令:
python lesson_01_05.py预期输出
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输出分析
等概率成功查询:
10 20 30 40 50比较次数分别为:
1 2 3 4 5平均值为 3.0。前部高频查询:
10 10 10 20 30比较次数为:
1 1 1 2 3平均值为 1.6。未命中高频查询:
10 99 99 99 99比较次数为:
1 5 5 5 5平均值为 4.2。这说明平均情况由真实查询分布决定。
Tips
- 最好情况通常不能代表稳定性能。
- 最坏情况适合评估性能上界。
- 平均情况必须说明输入分布。
- 目标不存在也属于重要输入情况。
- 提前返回会产生不同执行路径。
- 相同大 O 复杂度下,平均比较次数可能不同。
- 工程系统还需要关注 P95 和 P99。
- 对强实时系统,应优先保证最坏情况可控。
- 对批处理系统,可以更关注总体吞吐量。
- 测试平均性能时,需要使用代表真实业务的数据分布。
- 不要使用过于理想的随机数据替代真实负载。
- 复杂度分析与生产监控应结合使用。
常见错误
错误一:只报告最好情况
目标位于首位时很快,不代表其他输入也快。
错误二:把平均情况理解为最好与最坏的简单平均
平均情况需要对所有可能输入及其概率进行加权。
错误三:不说明目标是否存在
目标不存在时,线性查找通常需要扫描全部元素。
错误四:默认所有输入等概率
真实业务中,热门数据和冷门数据的访问概率通常不同。
错误五:用一次运行结果代表算法性能
单次运行可能受到系统负载、缓存和偶然因素影响。
错误六:只看平均值
平均值可能掩盖少量非常慢的请求。
错误七:把复杂度相同理解为性能完全相同
两个 O(n) 算法可能有不同常数开销、缓存行为和提前退出概率。
本课练习
- 计算长度为 10 的列表中,目标等概率存在时的平均比较次数。
- 分析目标不存在概率为 50% 时,线性查找平均比较次数如何变化。
- 修改示例,使查询更集中在列表尾部。
- 记录不同查询分布下的平均比较次数。
- 分析二分查找的最好和最坏情况。
- 分析冒泡排序在已排序输入和逆序输入下的差异。
- 思考支付接口为什么更关注最坏延迟和 P99。
- 思考离线统计为什么更关注总吞吐量。
- 设计一个查询分布,其中线性查找平均只需要接近一次比较。
- 设计一个查询分布,其中线性查找平均接近 n 次比较。