知识卡片
用比较次数分析快排
快排每次分区都会将一个枢轴排除出后续递归,因此分区调用至多 n 次。若 X 是所有分区中的元素比较总次数,循环总成本与 X 成正比,调用和循环外开销合计 O(n),故总时间 O(n+X)。分析随机快排时可先求 E[X]。
这张卡片看不懂?
这张卡片的反馈已满 10 条,暂时无法继续提交。
已有反馈 · 0 / 10 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- 第7章 快速排序 · 查看原书依据
The running time of QUICKSORT on an n-element array is O(n + X), where X is the number of element comparisons performed.
参考来源
- 位置:《算法导论(第4版)》第 7 章 7.4.2 节(`OEBPS/chapter007.xhtml`,文本字符 [20000, 25500);Art_P315–P321)。
- 结论依据:引理 7.1 按枢轴一次性退出递归和分区循环比较次数拆解总成本。
- 原始内容:The running time of Q UICKSORT on an n -element array is O ( n + X ), where X is the number of element comparisons performed.