面试题库 › C++ / 后端 › 快速排序时间复杂度的证明方法

快速排序时间复杂度的证明方法

难度 ★★★在 1 场真实面经中被问到 方向:C++ / 后端考点:排序算法

哪些公司问过

Intel1

常见岗位:C/C++ 软件开发

答案要点

  1. 平均情况递推式 T(n)=n−1+(2/n)·ΣT(k),可用代入法加归纳证明
  2. 求和项可以用积分近似估计
  3. 指示器随机变量:zi 与 zj 比较的概率为 2/(j−i+1)
  4. 期望比较次数约 2n ln n,即 O(n log n)
  5. 最坏划分 T(n)=T(n−1)+O(n),为 O(n²)

易错点

面试官常见追问

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

相关面试题