知识卡片
桶大小平方和决定成本
桶内使用插入排序时,总时间可写为 Θ(n)+ΣO(n_i²),其中 n_i 为第 i 个桶的大小。
均匀独立输入使 E[n_i²]=2−1/n,故期望总时间 Θ(n);更一般地,只要桶大小平方和是 O(n),即便输入不均匀也能线性运行。
这张卡片看不懂?
这张卡片的反馈已满 10 条,暂时无法继续提交。
已有反馈 · 0 / 10 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- 第8章 线性时间排序 · 查看原书依据
As long as the input has the property that the sum of the squares of the bucket sizes is linear in the total number of elements, equation (8.1) tells us that bucket sort runs in linear time.
参考来源
- 位置:《算法导论(第4版)》第 8 章 8.4 节(`OEBPS/chapter008.xhtml`,文本字符 [25000, 27300);Art_P328–P332)。
- 结论依据:原文将桶内成本表示为桶大小的平方和,以二项分布二阶矩得到期望界,并给出更一般条件。
- 原始内容:As long as the input has the property that the sum of the squares of the bucket sizes is linear in the total number of elements, equation (8.1) tells us that bucket sort runs in linear time.