知识卡片

普通读书笔记卡 · 3617

桶排序依赖均匀分布

理解等级:中级

桶排序把 [0,1) 划为 n 个等宽桶,用 ⌊n·x⌋ 将输入 x 放入相应桶;桶内排序后按桶号拼接。

跨桶次序由区间位置保证,同桶次序由局部排序保证。

本章用输入独立且均匀作为证明期望线性时间的一项充分假设,使桶内元素数通常很小;非均匀输入也可能线性。

这张卡片看不懂?

已有反馈 · 0 / 10 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    参考来源

    - 位置:《算法导论(第4版)》第 8 章 8.4 节(`OEBPS/chapter008.xhtml`,文本字符 [21500, 25300);图 8.4/Art_P327)。 - 结论依据:8.4 节用独立均匀分布推得桶大小平方和的期望为 O(n),从而证明期望线性;节末指出非均匀输入只要桶大小平方和为 O(n) 也可线性。 - 原始内容:Bucket sort assumes that the input is drawn from a uniform distribution and has an average-case running time of O ( n ).