知识卡片
顺序统计量是第i小元素
第 i 顺序统计量是 n 个数中第 i 小者。
先完整排序再取第 i 项可行,却做了多余工作;本书指出可直接选择,在任意实数输入上达到 O(n) 最坏界,随机版本则达 O(n) 期望界。
这张卡片看不懂?
这张卡片的反馈已满 10 条,暂时无法继续提交。
已有反馈 · 0 / 10 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- 第二部分 排序和顺序统计量 · 查看原书依据
The ith order statistic of a set of n numbers is the ith smallest number in the set.
参考来源
- 位置:《算法导论(第4版)》Part II 引言(`OEBPS/part002.xhtml`,文本字符 [5000, 8221);输出序列图 Art_P297a–P297b)。
- 结论依据:Part II 引言定义第 i 顺序统计量为第 i 小元素,并说明第 9 章给出期望 O(n) 的随机选择和最坏 O(n) 的确定性选择。
- 原始内容:The i th order statistic of a set of n numbers is the i th smallest number in the set.