知识卡片
桶排序依赖均匀分布
桶排序把 [0,1) 划为 n 个等宽桶,用 ⌊n·x⌋ 将输入 x 放入相应桶;桶内排序后按桶号拼接。
跨桶次序由区间位置保证,同桶次序由局部排序保证。
本章用输入独立且均匀作为证明期望线性时间的一项充分假设,使桶内元素数通常很小;非均匀输入也可能线性。
这张卡片看不懂?
这张卡片的反馈已满 10 条,暂时无法继续提交。
已有反馈 · 0 / 10 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- 第8章 线性时间排序 · 查看原书依据
Bucket sort assumes that the input is drawn from a uniform distribution and has an average-case running time of O(n).
参考来源
- 位置:《算法导论(第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 ).