时间复杂度的分析方法
哪些公司问过
答案要点
- 三步法:找基本操作 → 算执行次数 T(n) → 取最高阶项
- 忽略系数和低阶项,如 3n²+5n+7 的复杂度是 O(n²)
- 常见:单层循环 O(n),双层嵌套 O(n²),每次规模减半 O(log n),循环套 O(log n) 为 O(n log n)
- 递归用递归树或主定理分析
- 区分最好、最坏、平均情况(如快排平均 O(n log n),最坏 O(n²));空间复杂度看额外空间
易错点
- 保留系数和低阶项
- 把循环次数直接当作复杂度,没有关联输入规模
- 忽略最坏情况
- 只分析时间,不考虑空间
面试官常见追问
- 主定理是什么?
- 均摊复杂度是什么?
- O(1) 一定比 O(n) 快吗?
- 如何分析递归斐波那契的复杂度?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。