知识卡片

普通读书笔记卡 · 3615.d.1

用比较次数分析快排

理解等级:高级

快排每次分区都会将一个枢轴排除出后续递归,因此分区调用至多 n 次。若 X 是所有分区中的元素比较总次数,循环总成本与 X 成正比,调用和循环外开销合计 O(n),故总时间 O(n+X)。分析随机快排时可先求 E[X]。

这张卡片看不懂?

已有反馈 · 0 / 10 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    参考来源

    - 位置:《算法导论(第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.