知识卡片

普通读书笔记卡 · 5654.c.1.a.2.a.2.a.23 · 生成模型:未记录

桶排序依赖分布与保序映射

理解等级:中级

把元素分配到有序的桶,对每桶排序,再按桶序连接。正确性需要较早桶中的元素不大于较晚桶中的元素;普通散列函数通常不保序。桶内使用插入排序时,工作量与 Σ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的期望值。这个计算是非常关键的,因为这是决定插入排序开销的关键因素,插入

    参考来源

    - 位置:《算法技术手册》第4章《桶排序》(spine1522;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1485.html;u097-ch04-024)。 - 结论依据:97全文和03221伪代码实读;复杂度和反例由桶内插入排序推导。 - 原始内容:桶排序 当计算集合中的n个元素时,如果能够构建一个小得多的k个值的集合,那么这个时候就可以使用计数排序。给定n个元素的集合,桶排序构造了n个桶来切分输入集合,因此桶排序能够降低处理时其在额外空间的开销。如果一个散列函数,hash(Ai),用来均匀地将n个元素分配到n个桶中,那么如图4-18所示的桶排 - 位置:《算法技术手册》第4章《使用环境》(spine1523;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1486.html;u098-ch04-024)。 - 结论依据:98称均匀分配时最快;性能结论仍取决于具体实现、分布和对照算法。保序是正确性要求,均匀分布主要影响桶内排序成本。 - 原始内容:均匀分配时,桶排序是最快的排序法。 - 位置:《算法技术手册》第4章《驱动因素》(spine1524;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1487.html;u099-ch04-024)。 - 结论依据:99强调存储与全序;全序并不自动提供高效均匀映射,实际还需考虑键分布、桶数组和桶内元素存储。 - 原始内容:全序关系,桶排序就能够利用这些信息,节省大量开销。 - 位置:《算法技术手册》第4章《分析》(spine1526;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1489.html;u101-ch04-024)。 - 结论依据: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);这是概率模型下的期望,不是每个输入的最坏保证。 - 原始内容:Var[ni]=n*p*(1-p)=(1-1/n)。考虑方差是非常重要的,因此有些桶可能是空的,而其他的可能有多于一个元素;我们需要保证没有桶包含过多的元素。我们再一次通过统计理论得到下面的等式: 从这个等式我们能够计算出ni2的期望值。这个计算是非常关键的,因为这是决定插入排序开销的关键因素,插入