知识卡片
桶排序依赖分布与保序映射
把元素分配到有序的桶,对每桶排序,再按桶序连接。正确性需要较早桶中的元素不大于较晚桶中的元素;普通散列函数通常不保序。桶内使用插入排序时,工作量与 Σni² 有关,ni 为各桶元素数。
独立均匀输入、n 个等宽桶的模型下期望总时间为 O(n),但所有元素落入同一个桶时仍可能达到 O(n²),因此书中图示和正文给出的无条件最坏线性不成立。桶数组及元素存储也需计入空间。
98称均匀分配时最快;性能结论仍取决于具体实现、分布和对照算法。保序是正确性要求,均匀分布主要影响桶内排序成本。
99强调存储与全序;全序并不自动提供高效均匀映射,实际还需考虑键分布、桶数组和桶内元素存储。
101在 n 个独立均匀分配到 n 个桶的模型下,E[ni]=1、Var(ni)=1−1/n,由 E[ni²]=Var(ni)+E[ni]² 得 E[ni²]=2−1/n。各桶期望平方和为 O(n),故桶内插入排序总期望 O(n);这是概率模型下的期望,不是每个输入的最坏保证。
这张卡片看不懂?
这张卡片已通过人工审查,不再接受失败反馈。
已有反馈 · 0 条
还没有人提交反馈。
在整书笔记中的位置
- · 桶排序依赖分布与保序映射
- · 使用环境
- · 驱动因素
- · 分析
原书出处 · 4 处
- · 查看原书依据
桶排序 当计算集合中的n个元素时,如果能够构建一个小得多的k个值的集合,那么这个时候就可以使用计数排序。给定n个元素的集合,桶排序构造了n个桶来切分输入集合,因此桶排序能够降低处理时其在额外空间的开销。如果一个散列函数,hash(Ai),用来均匀地将n个元素分配到n个桶中,那么如图4-18所示的桶排
- · 查看原书依据
均匀分配时,桶排序是最快的排序法。
- · 查看原书依据
全序关系,桶排序就能够利用这些信息,节省大量开销。
- · 查看原书依据
Var[ni]=n*p*(1-p)=(1-1/n)。考虑方差是非常重要的,因此有些桶可能是空的,而其他的可能有多于一个元素;我们需要保证没有桶包含过多的元素。我们再一次通过统计理论得到下面的等式: 从这个等式我们能够计算出ni2的期望值。这个计算是非常关键的,因为这是决定插入排序开销的关键因素,插入