知识卡片
随机划分保证的是期望行为
随机化算法用随机选择影响求解过程。快速排序可随机选择枢轴,再把元素分到其两侧;极不平衡的划分仍可能出现,因此“随机”不是每次都选中位数或把两侧平分。
对常见随机枢轴方案的效率解释应区分单次结果与随机选择下的期望,不能用本次恰好平衡来证明整体性能。原文用“随机数的正态分布”解释平衡不准确:标准随机枢轴分析不以正态分布为前提。
边界核验:MIT 6.046J讲义区分固定端点枢轴退化与随机枢轴的期望复杂度;这里只纠正该解释,详细证明留后文。
41把随机快排列为使用概率分析的例外。应区分对输入分布平均与固定输入下对随机选择取期望;不能把“概率基础”说成每次性能都等于平均或最坏已消失。
208随机选取及三样本选择仍可能不平衡,不能保证任意一次都接近中位。此前MIT随机化讲义已核验期望O(n log n)而非去掉平方最坏;本书具体三样本代码还有选下标而非值的问题在210单列。
这张卡片看不懂?
这张卡片已通过人工审查,不再接受失败反馈。
已有反馈 · 0 条
还没有人提交反馈。
在整书笔记中的位置
- · 随机划分保证的是期望行为
- · 为什么要做最坏情况分析
- · 快速排序的描述
原书出处 · 3 处
- · 查看原书依据
随机选择一个支票号码作为划分的依据。快速排序的平均性能很不错,因为随机数的正态分布使得划分的结果是相对平衡的。 分治法 分治法包含3个步骤:分解、求解与合并。在分解阶段,将数据分解为更小、更容易管理的部分。在求解阶段,对每个分解出的部分进行处理。在合并阶段,将每部分处理的结果进行合并。一个分治法的例
- · 查看原书依据
随机算法中的快速排序算法(见第12章),它使用了概率论的理论基础,从而有效地保证了平均情况下性能的准确性。
- · 查看原书依据
随机选择法来选取。据统计,即便试图故意让算法陷入瘫痪,随机选择也能够有效地防止被分割的数据极度不平衡。同时,还可以改进这种随机选择方法,方法是首先随机选择三个元素,然后选择三个元素中的中间值。这就是所谓的中位数方法,可以保证平均情况下的性能。由于这种分割方法依赖随机数的统计特性,从而保证快速排序的整