知识卡片

普通读书笔记卡 · 3617.a

桶大小平方和决定成本

理解等级:高级

桶内使用插入排序时,总时间可写为 Θ(n)+ΣO(n_i²),其中 n_i 为第 i 个桶的大小。

均匀独立输入使 E[n_i²]=2−1/n,故期望总时间 Θ(n);更一般地,只要桶大小平方和是 O(n),即便输入不均匀也能线性运行。

这张卡片看不懂?

已有反馈 · 0 / 10 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    参考来源

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