知识卡片

普通读书笔记卡 · 3615.d

随机枢轴消除固定坏输入

理解等级:中级

随机化快排从当前子数组均匀选一个枢轴,交换到末位后沿用普通分区。

对固定输入,分区质量由算法内部随机选择决定,因此不存在仅由元素顺序确定的坏输入;但单次仍可能遇到连续差枢轴,最坏时间仍为 Θ(n²)。

这张卡片看不懂?

已有反馈 · 0 / 10 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    参考来源

    - 位置:《算法导论(第4版)》第 7 章 7.1–7.3 节(`OEBPS/chapter007.xhtml`,文本字符 [15000, 20000);图 7.1–7.5)。 - 结论依据:7.3 节 RANDOMIZED-PARTITION 从当前子数组等概率选枢轴并与末位交换;随机选择改变固定输入的划分分布,仍保留 Θ(n²) 最坏路径。 - 原始内容:Instead of always using A [ r ] as the pivot, a randomized version randomly chooses the pivot from the subarray A [ p : r ]