什么情况下算法时间复杂度最差
哪些公司问过
答案要点
- 最坏情况是规模 n 下运行步数最多的输入,给出时间上界
- 最坏情况与平均、最好情况分开分析,取决于实现和输入分布
- 快排固定取首尾为基准,遇到有序或逆序输入时退化为 O(n²)
- BST 有序插入退化为链表、哈希大量冲突,都会使查找退化为 O(n)
- 随机基准、三数取中、平衡树、良好哈希函数可规避最坏情况
易错点
- 把最坏情况等同于大 O,混淆情况分析和渐近记号
- 说快排最坏情况时不说明基准选取方式这个前提
- 只背结论,说不清是哪种输入导致退化
面试官常见追问
- 快排怎么避免最坏情况?
- 大 O、大 Θ、大 Ω 有什么区别?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。