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