知识卡片
秩距离决定比较概率
在元素互异且枢轴均匀随机选择时,Z_ij 中任一元素成为首个枢轴的概率相同。只有两个端点触发 z_i 与 z_j 比较,故概率为 2/(j−i+1)。若有同值键,需另处理,不能直接沿用此式。
这张卡片看不懂?
这张卡片的反馈已满 10 条,暂时无法继续提交。
已有反馈 · 0 / 10 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- 第7章 快速排序 · 查看原书依据
the probability that they are compared is 2/(j – i + 1).
参考来源
- 位置:《算法导论(第4版)》第 7 章引理 7.3(`OEBPS/chapter007.xhtml`,文本字符 [27000, 29300);Art_P315–P321)。
- 结论依据:引理 7.2 的比较条件加上区间内均匀枢轴选择。
- 原始内容:the probability that they are compared is 2/( j – i + 1).