桶式排序分析
桶式排序分析
提问于 2011-10-01 09:39:55
一个简单的例子是桶排序。要使桶排序工作，必须提供额外的信息。输入a1，a2，。。。，必须只由小于m的正整数组成(显然，这是可能的扩展)。如果是这样的话，那么算法很简单:保持一个名为count的数组，大小为m，初始化为所有的0。因此，count有m个单元或桶，最初是空的。在读取ai时，增加1。在读取所有输入后，扫描计数数组，打印出排序列表的表示形式。该算法取O(m +n)，如果m为O(n)，则总数为O(n)。
虽然这个算法似乎违反了下界，但它并不是因为它使用了比简单比较更强大的操作。通过增加适当的桶，该算法实质上是在单位时间内进行m-路比较.这类似于可扩展散列中使用的策略。这一点显然不在证明下限的模型中。
我对上段的问题
作者所说的“它使用比简单的comparisons"?
- By增量适当的桶更强大的操作，算法如何执行m-way比较”是什么意思？顺便说一句，上面提到的m-way comparision?
- How与可扩展散列相关的是什么？请给出一个可扩展散列的例子吗？
谢谢!
回答 1
Stack Overflow用户
回答已采纳
发布于 2011-10-01 09:47:23
-
count[arr[i]]比*(count + arr[i])更“强大”，因为它实际上是*(count + arr[i])。每个比较op有两个可能的值: true/false，而这个op有更大范围的值，所有可能的地址！因此，通过增加元素， - 变得更加“强大”，算法“知道”在这个“桶”中有多少个元素，然后“泄漏”这个桶的内容即可。作者所指的m路比较，我假设是与m可能输出的“比较”，正如我前面所解释的，
- --这基本上是一种散列，您将元素散列到范围
[0,m]。这里的重要性和区别是:两个元素被散列为相同的数字，当且仅当它们是相同的。当然，只有当哈希元素的范围相同或小于图像时，才能实现这一点。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/7619423
复制相关文章
相似问题
腾讯云开发者
