如果我们知道数组中的所有元素都以给定数字为上限，则计数排序是线性时间的。如果我们取一个通用数组，我们不能只在线性时间内扫描数组，找到数组中的最大值然后应用计数排序吗？
问问题
1304 次
3 回答
8
知道运行计数排序的上限是不够的：您需要有足够的内存来容纳所有计数器。
考虑一种情况，当您遍历一个 64 位整数数组时，发现最大元素是 2^60。这意味着两件事：
- 你需要一个 O(2^60) 内存，并且
- 完成排序需要 O(2^60)。
O(2^60)相同的事实O(1)在这里没有什么帮助，因为常数因子太大了。这通常是伪多项式时间算法的问题。
于 2014-07-28T18:33:05.020 回答
2
假设最大的数字是 235684121。那么您将花费大量的 RAM 来保存您的存储桶。
于 2014-07-28T18:31:30.540 回答
0
我想提一下@dasblinkenlight 和@AlbinSunnanbo 的答案，你想通过扫描数组O(n)来找到数组中的最大值是可以的。以下来自维基百科：
但是，如果 k 的值未知，则可以通过对数据的附加循环来计算它，以确定数据中实际出现的最大键值。
由于时间复杂度应该O(n + k)并且k应该在一定限度内，因此您的发现k应该很小。正如@dasblinkenlight 提到的，O(large_value)实际上不能收敛到O(1).
虽然到目前为止我不知道计数排序的任何主要应用，除了用作Radix Sort 的子程序，它可以很好地用于字符串排序（即排序“android”到“addnoir”）等问题，因为这里k只有 255 .
于 2014-07-28T22:23:58.237 回答