知识卡片
随机选择的期望收缩
在元素互异(或先以原下标打破同值)时,若枢轴落在中间一半,本轮至少剔除四分之一,留下至多 3n/4 个元素;随机枢轴产生这种“有用划分”的概率至少一半。因此,每次有用划分出现前所需划分轮数的期望至多为 1/(1/2)=2,而各阶段处理规模形成 n+3n/4+(3/4)²n+⋯≤4n 的几何级数;每阶段再乘至多 2 轮,期望总工作量仍为 O(n)。连续极端枢轴仍可能带来 Θ(n²) 最坏时间。
这张卡片看不懂?
这张卡片的反馈已满 10 条,暂时无法继续提交。
已有反馈 · 0 / 10 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- 第9章 中位数和顺序统计量 · 查看原书依据
A partitioning is helpful with probability at least 1/2.
参考来源
- 位置:《算法导论(第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.