面试题库 › C++ / 后端 › 算法的最优情况与最坏情况复杂度

算法的最优情况与最坏情况复杂度

难度 ★☆☆在 1 场真实面经中被问到 方向:C++ / 后端考点:复杂度分析

哪些公司问过

深信服1

常见岗位:Python 后端

答案要点

  1. 最优、最坏是对同规模 n 的所有输入而言,分别取运行时间最少和最多的输入
  2. 典型例子:插入排序最优 O(n)、最坏 O(n²);快速排序最坏 O(n²)、平均 O(n log n)
  3. 最坏情况给出性能上限保证,工程和实时系统中最常用
  4. 平均情况需要假设输入分布;最优情况只在特殊输入下出现,参考价值有限
  5. 大 O 是上界记号,与最坏情况是两个概念,任一种情况都可用 O、Ω、Θ 描述

易错点

面试官常见追问

完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。

相关面试题