算法的最优情况与最坏情况复杂度
哪些公司问过
答案要点
- 最优、最坏是对同规模 n 的所有输入而言,分别取运行时间最少和最多的输入
- 典型例子:插入排序最优 O(n)、最坏 O(n²);快速排序最坏 O(n²)、平均 O(n log n)
- 最坏情况给出性能上限保证,工程和实时系统中最常用
- 平均情况需要假设输入分布;最优情况只在特殊输入下出现,参考价值有限
- 大 O 是上界记号,与最坏情况是两个概念,任一种情况都可用 O、Ω、Θ 描述
易错点
- 把最优情况理解为 n 很小的情况,应是同一规模下最有利的输入
- 认为大 O 就等于最坏情况复杂度
- 用最优情况来评价算法性能
面试官常见追问
- 平均情况复杂度和均摊复杂度有什么区别?
- 如何避免快速排序退化到最坏情况?
- 为什么哈希表查找常说是 O(1)?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。