为什么计数排序不适用于大规模输入？

Question

计数排序是一种平均时间复杂度为O(n+K)的排序算法，它假设输入元素都是0到K范围内的整数。为什么不能在未排序的数组中进行线性搜索最大值，将其等于K，然后应用计数排序呢？

- shauryachats

---

大多数情况下，您不仅要对整数进行排序。您还需要将它们与其附带数据一起排序。简单的计数排序无法做到这一点。 - liori

空间复杂度是一个问题。但是一般来说，你可以做到。只是对于中等规模的范围来说速度会比较慢。 - keyser

你实际上是什么意思说“内存写入是免费的”？请记住，比较复杂对象和结构也是计算成本的一部分。 - JP Ventura

实际上，计数排序确实比其他基于比较的排序算法使用更多的内存。因此，我只是想比较计数排序的算法方面。 - shauryachats

那个语句并没有太多意义，因为计数排序的时间复杂度和空间复杂度都是相同的：Ω(n + K)。 - Niklas B.

抱歉，已经编辑了问题。 - shauryachats

Answer 1

在您的输入是具有maximum - minimum = O(n log n)（即值的范围相当受限）的数组的情况下，计数排序确实是有意义的。如果不是这种情况，则标准的基于比较的排序算法甚至像基数排序这样的整数排序算法在渐近意义下更好。

举个例子，以下算法生成的一组输入使得计数排序的运行时间复杂度为Θ(n^2):

def generate_input(n):
    array = []
    for i := 1 to n:
        array.append(i*i);
    shuffle(array)
    return array

- Niklas B.

---

请问您能解释一下 K = O(n log n) 是什么意思吗？我的意思是，这里的 K 是一个常数。一个常数怎么可能有时间复杂度呢？ - shauryachats

不，K不是一个常数。K是输入的一个函数。请记住，Landau O符号可以用于任意数学函数，而不仅仅是表示指令计数/运行时间的函数。 - Niklas B.

@Joao：设f(n)为计数排序在给定输入族上的运行时间。我们有f(n) = Θ(n + k) = Θ(n^2)，因此我的说法是正确的。 - Niklas B.

根据Thomas Cormen的《算法导论》一书，计数排序的时间复杂度为Ω(n + k)和O(n + k)，如果k是O(n)。因此，如Niklas所述，使用比数组长度大得多的数字违反了使Θ(n + k)成立的前提条件。因此，如果数组中存在k = Θ(nˆ2)，则时间复杂度变为Θ(n^2)。 - JP Ventura

Answer 2

你的问题标题是为什么不使用计数排序来处理大量数据？

计数排序是如何运作的呢？我们需要另一个数组（假设为b[]）并将所有元素初始化为0。然后，如果给定数组中存在某个索引，我们就会增加该索引。接下来，我们从给定数组的下限到上限运行循环，并检查我所采取的数组（b[]）的索引元素是否为0。如果不为零，则意味着该索引是给定数组的一个元素。

现在，如果这两个值（上限和下限）之间的差距非常高（例如10^9或更高），那么单个循环足以使我们的电脑崩溃 :)

- Mukit09

---

我希望那个问题会出现。我想如果我们可以使用std::map来索引那个数组的元素。唯一的问题是要跟踪现有的元素，所以需要另一个std::set。这是一种比较朴素的方法，如果你能告诉我更好的方法就好了。 - shauryachats

@ShauryaChats 插入 std::set 和 std::map 的时间复杂度为 O(log n)，这破坏了计数排序的优势。你不能使用哈希表，因为你需要按排序顺序迭代现有元素。但如果你能做到后者，你就不需要再排序了。 - Niklas B.

Answer 3

根据大O符号的定义，如果我们说f(n) ∈ O(g(n))，那么意味着存在一个值C > 0和n = N，使得f(n) < C*g(n)，其中C和N是常数。并没有说明C的值，也没有说明不等式对于哪个n = N成立。

在任何算法分析中，都必须考虑图灵机的每个操作的成本（比较、移动、求和等）。这些成本的值是决定C和N的大小（或小）的定义因素，以便使不等式成立或不成立。删除这些成本是一种天真的假设，我在算法分析课程中曾经使用过。

语句“计数排序是O(n+k)”实际上意味着，对于给定的C、n > N和n > K，排序是多项式和线性的，其中C、N和K是常数。因此，对于较小的输入，其他算法可能具有更好的性能，因为不等式仅在给定条件为真时才成立。

- JP Ventura