最好、最坏与平均情况
复习
- 大 O 记号：大 O 描述运行时间随规模增长的趋势
- 常见增长速度：从对数一路到指数
- 常数因子：规模不够大时，常数也可能左右胜负
TL;DR
- 同一个算法，面对不同输入，耗时可能相差很大
- 最好、最坏、平均，是三种不同的时间界限
- 工程上常常更关注最坏情况，因为它是一种保证
- 平均情况要成立，需要明确输入是怎么分布的
正文
到目前为止，我们总在说“这个算法是 O(n)”或“O(n²)”。但细想一下，同一个算法，碰到不同的输入，表现真的会一样吗？
看一个最简单的例子：在一列数据里查找某个目标。
- 如果目标恰好在第一个，一次就找到了
- 如果目标在最后，或者根本不存在，就得看完全部 n 个
- 如果目标位置随机，平均要看一半左右
同样是线性查找，最好、最坏、平均，差别明显。所以，说“某个算法多快”，往往要补一句：在哪种情况下？
三种界限
- 最好情况：运气最好时的耗时，通常参考价值有限
- 最坏情况：最倒霉时的耗时，是一种“最迟多久”的保证
- 平均情况：在所有输入上的平均耗时，最贴近日常体感
在我们之前的大 O 讨论里，除非特别说明，通常默认指的是最坏情况——也就是“最多不会超过这个量级”。
为什么更看重最坏
既然平均情况最贴近体感，为什么工程上还常常盯着最坏情况？
因为最坏情况是一种承诺。对于实时系统、飞行控制、医疗设备这类场景，“大多数时候很快”是不够的，必须保证“最迟也能在某个时限内完成”。平均情况再好，只要存在一个会突然卡死的输入，就可能酿成事故。
而最好情况则几乎没人当真：它只在最有利的输入下成立，参考价值最低。
平均情况，先问怎么平均
说到平均，还有一个容易忽略的前提：平均是对什么分布求的平均？
“目标位置均匀随机”是一种假设；“目标经常是高频查询的少数几个键”又是另一种。假设不同，算出的平均耗时可能完全不同。所以，平均情况不是一个放之四海而皆准的数，而是在某个明确假设下的结论。用之前，先问清楚它的前提。
思考题 1
为什么工程上通常更关注最坏情况，而不是平均情况？
思考题 2
“平均情况是
O(n)”这句话要成立，需要额外说明什么？
小结
知识点
- 同一算法在不同输入上耗时不同
- 最好、最坏、平均是三种时间界限
- 最坏情况提供一种保证，工程上最常被关注
- 平均情况依赖于对输入分布的假设
参考资料
- Wikipedia(zh)：最佳、最差和平均情况：算法在不同输入下的表现
- Wikipedia(zh)：时间复杂度：运行时间随规模的增长
思考题答案（仅供参考）
思考题 1
因为最坏情况是一种保证，而平均情况只是统计意义上的期望。对实时性要求高的场景，系统必须能应对最不利的输入，否则一次异常就可能造成严重后果。最坏情况给出了“最迟多久”的底线。
思考题 2
需要说明输入是按什么分布来的。比如“查找目标在任意位置等概率出现”，才会有“平均看一半”的结论。换一种分布，平均值就变了。所以脱离输入假设谈平均情况，是没有意义的。
协议
本作品采用知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议进行许可。
封面图
设计师 | 南国微雪