知识卡片

普通读书笔记卡 · 3612.a.2.a

随机选择的期望收缩

理解等级:高级

在元素互异(或先以原下标打破同值)时,若枢轴落在中间一半,本轮至少剔除四分之一,留下至多 3n/4 个元素;随机枢轴产生这种“有用划分”的概率至少一半。因此,每次有用划分出现前所需划分轮数的期望至多为 1/(1/2)=2,而各阶段处理规模形成 n+3n/4+(3/4)²n+⋯≤4n 的几何级数;每阶段再乘至多 2 轮,期望总工作量仍为 O(n)。连续极端枢轴仍可能带来 Θ(n²) 最坏时间。

这张卡片看不懂?

已有反馈 · 0 / 10 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    参考来源

    - 位置:《算法导论(第4版)》第 9 章 9.2 节(`OEBPS/chapter009.xhtml`,文本字符 [9500, 15500);Art_P341)。 - 结论依据:引理 9.1 将“中间一半”定义为剔除两端各 ⌈n/4⌉−1 个秩位;枢轴落其中时,至少一侧有这些元素及枢轴被排除,目标侧至多约 3n/4;该区域至少占一半秩位。最坏时间来自反复极端划分。 - 原始内容:A partitioning is helpful with probability at least 1/2.