为什么我们不能将计数排序应用于通用数组？

Question

如果我们知道数组中的所有元素都是由给定数字限定的,则计算排序是线性时间.如果我们采用一般数组,我们只能在线性时间扫描数组,找到数组中的最大值然后应用计数排序？

Answer 1

仅知道运行计数排序的上限是不够的:您需要有足够的内存来适应所有计数器.

考虑一种情况,当您浏览64位整数数组时,发现最大元素是2 ^ 60.这意味着两件事:

• 你需要一个O(2 ^ 60)内存,和
• 它将需要O(2 ^ 60)来完成排序.

这里的事实O(2^60)是相同的O(1),因为常数因素太大了.这通常是伪多项式时间算法的问题.

Answer 2

假设最大的数字类似于 235684121。那么您将花费大量的 RAM 来保存您的存储桶。