快速排序时间复杂度的证明方法
哪些公司问过
答案要点
- 平均情况递推式 T(n)=n−1+(2/n)·ΣT(k),可用代入法加归纳证明
- 求和项可以用积分近似估计
- 指示器随机变量:zi 与 zj 比较的概率为 2/(j−i+1)
- 期望比较次数约 2n ln n,即 O(n log n)
- 最坏划分 T(n)=T(n−1)+O(n),为 O(n²)
易错点
- 把平均复杂度当作对固定输入的结论,忽略是对随机排列或随机基准取期望
- 以为任何不均衡划分都会退化为 O(n²)
- 代入法证明时常数 c 没处理清楚
面试官常见追问
- 主定理能直接用于快排吗?
- 按 1:9 划分也是 O(n log n) 吗?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。
相关面试题
- 快速排序的原理与实现155 场
- 常见排序算法的对比129 场
- 排序算法的稳定性58 场
- 归并排序的实现与特点24 场
- 堆排序的实现21 场
- 外排序:10 亿个整数如何排序14 场
- C++ std::sort 的内部实现7 场
- 手写实现一种数组排序算法7 场
- 快速排序的最坏情况与优化方法7 场
- 冒泡排序与快速排序的原理与区别6 场