知识卡片

普通读书笔记卡 · 3612

顺序统计量是第i小元素

理解等级:初级

第 i 顺序统计量是 n 个数中第 i 小者。

先完整排序再取第 i 项可行,却做了多余工作;本书指出可直接选择,在任意实数输入上达到 O(n) 最坏界,随机版本则达 O(n) 期望界。

这张卡片看不懂?

已有反馈 · 0 / 10 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    参考来源

    - 位置:《算法导论(第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.