6

如果我们知道数组中的所有元素都以给定数字为上限,则计数排序是线性时间的。如果我们取一个通用数组,我们不能只在线性时间内扫描数组,找到数组中的最大值然后应用计数排序吗?

4

3 回答 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 回答