计数排序的运行时间

Question

我希望你能帮我翻译计数排序的运行时间。在我的笔记中，它说假设数组A的大小为n，k是每个数字出现的次数，

 Counting-Sort(A,k) {
   for (i=1; i <= k; i++) // initialize number counters to 0
       times[i] = 0;

   for (j=1; j <= length[A]; j++) // decide how many times each
       times[A[j]]++;                  // number appears in the input

  // form the sorted array
  m=1;
    for ( i=1; i <= k; i++)    // consider each number in the range
         for ( j=1; j <= times[ i ]; j++) { // generate that number in 
            A[m]=i;                   // the output as many times as
            m++;                      // it occurs in the input
         }
  }

当我们看底部代码中的嵌套循环时，请注意每次内部循环迭代时，我们都会将一个新数字放入输出数组的正确位置。 因此：sum t_i（从 i = 1 到 k）= n。我不明白为什么这个总和等于 n。外部循环迭代 k 次，内部循环最多可能迭代 n 次，因此必须是 O(nk)。有人可以解释一下吗？谢谢

- user2110714

---

创建一个小的示例数组，并手动或使用程序填充times，很明显最内层循环总共最多只会执行n次，而不是nk次。 - Bernhard Barker

它实际上需要2n+k时间，O（n+k），请查看：http://en.wikipedia.org/wiki/Counting_sort - Khaled.K

Answer 1

算法

计数排序，也称为直方图排序。

n = length of input Array

k = number of unique symbols that appear in the input Array

• 初始化需要 k 时间

• 计算需要 n 时间

• 枚举需要 Sum { Count(i) } = n 时间

复杂度

Time = k + n + n = 2n+k

Time ~ O(2n+k) = O(n+k)

Space = n + k ~ O(n+k)

- Khaled.K

Answer 2

正如你所看到的循环

m=1;
for ( i=1; i <= k; i++)    // consider each number in the range
     for ( j=1; j <= times[ i ]; j++) { // generate that number in 
        A[m]=i;                   // the output as many times as
        m++;                      // it occurs in the input
     }

它的复杂度将等于内部循环体被执行的次数。当i = 1时，它被执行times [1]次，当i = 2时，它被执行times [2]次，以此类推，当i = k时，times [k]次。因此，总的内部循环体被执行了times [1] + times [2] + ... + times [k]次，而该总和等于n，因为每个元素只计算一次。

- artahian

---

那个循环只是完整算法的一部分，分析不完整。 - Khaled.K

问题完全是关于代码的这部分，其他部分很明显。 - artahian

@aram90。times[1]+times[2]+...+times[k] 怎么会加起来等于1？因为'times'数组存储了每个元素的计数，请澄清一下。 - CKM

@chandresh，它不是加到1，而是加到n。 - artahian

Answer 3

这些笔记并不完全正确。 k 是出现在数组中的最大数字（即它包含从1到k的数字）。因此，让我们逐步了解算法：

1. 初始化 k 个“箱子”：O(k)
2. 计算每个数字出现的次数：O(n)
   • 所有箱子中值的总和恰好为 n，因为这是数组中总共有多少条目
3. 遍历所有箱子：O(k)
   • 在结果数组中设置与箱子表示的元素数量相同的元素：看似 O(n)

重要的是，我们知道，即使我们遍历了 k 个箱子，并且通常情况下每个箱子可能代表多达 n 个值，但我们设置了箱子，以便在外部循环的所有迭代中，内部循环仍然总共运行 n 次。因此，这一步的总复杂度实际上是 O(n)。

如果我们忽略了对箱子内容的额外知识，你就是完全正确的。

现在有一个最后的转折：如果 k > n，那么它实际上是 O(k) 而不是 O(n)！因为现在外部循环是“运行更频繁”的东西。

我希望这有些意义。

- Jan Krüger

---

k不能大于n，k是times数组的大小，该数组存储输入数组A中唯一值的直方图，其中n是输入数组A的大小。请参阅：http://en.wikipedia.org/wiki/Counting_sort - Khaled.K

@KhaledAKhunaifer k 可以比 n 更大。考虑数组 [1, 2, 100]。n 是3，但 k 是100。 - gsgx

@gsingh2011 k 不是数组中的最大值，而是数组中唯一值的数量。 - Khaled.K

从您发布的链接中可以看到：“计数排序的输入由n个项目组成，每个项目都有一个非负整数键，其最大值不超过k”。这意味着k定义了上限，或者说最大值是k。在计数排序中，您不知道有多少个唯一元素。对于[1, 2, 100]，您将使用大小为100的输出数组（最大值），而不是3（唯一值的数量）。 - gsgx

@gsingh2011 你说得对，但也要注意到在时间复杂度中不应该出现 k，除非我们考虑空间管理... 因为我们正在处理数组，而不是整个频率列表。 - Khaled.K