计数排序被称为线性时间如果我们知道,数组中的所有元素都是由上给定数量的限制。如果我们把一个普通的数组,不能我们只是扫描数组中的线性时间,找到数组中的最大值,然后申请计数排序?
Counting sort is known with linear time if we know that all elements in the array are upper bounded by a given number. If we take a general array, cant we just scan the array in linear time, to find the maximum value in the array and then to apply counting sort?
这是不够的,知道的上限运行计数排序:你需要有足够的内存来容纳所有的柜台
It is not enough to know the upper bound to run a counting sort: you need to have enough memory to fit all the counters.
考虑这样一种情况,当你经过的64位整数数组,并找出最大的因素是2 ^ 60。这意味着两件事情:
Consider a situation when you go through an array of 64-bit integers, and find out that the largest element is 2^60. This would mean two things:
您需要的O(2 ^ 60)内存,以及 这是要带O(2 ^ 60)来完成排序。事实上, O(2 ^ 60)
是一样的 O(1)
帮助不大在这里,因为常数因子是太大了。这是很经常与伪多项式时间算法的问题。
The fact that O(2^60)
is the same as O(1)
is of little help here, because the constant factor is simply too large. This is very often a problem with pseudo-polynomial time algorithms.