4

I am trying to understand the running time of counting sort. In my notes, it says, assuming the size of the array A is n, and k is the number of times each number occurs,

 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
         }
  }

Let ti denote the number of times the inner loop iterates for each i. When we look at the nested for loops at the bottom of the code, note that, every time the inner loop is iterated, we are placing a new number into its correct place in the output array. Hence: sum ti (from i=1 to k) = n.

I don't understand why this sum is equal to n. The outer loop iterates k times, and inner loop may iterate at most n times, so it must be O(nk). Can somebody explain? Thanks

4

3 回答 3

3

算法

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

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)
于 2013-03-22T07:15:48.223 回答
0

注释并不完全正确。k是您的数组中显示的最大数字（即它的数字从 1 到 k）。所以，让我们逐步完成算法：

  1. 初始化k“垃圾箱”：O(k)
  2. 计算每个数字出现的频率：O(n)
    • 所有 bin 中的值的总和正好是n，因为这就是我们在数组中总共有多少条目
  3. 遍历箱：O(k)
    • 在结果数组中设置与 bin 所代表的一样多的元素：看似O(n)

这里重要的是我们知道，即使我们迭代kbin 并且通常可以达到n每个 bin 表示的值，我们设置 bin 以便在外部循环的所有迭代中，内部循环循环仍然运行总n次数。因此，这一步的总复杂度实际上是O(n)。

如果我们忽略了我们对垃圾箱内容的额外了解，那么您绝对是对的。

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

我希望这有点道理。

于 2013-03-21T13:21:46.377 回答
0

正如你所看到的循环

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]次数, when i = 2=>times[2]次, 如此, when i = k,times[k]次。因此，内部主体总共执行了times[1] + times[2] + ... + times[k]几次，并且该总和等于n，因为每个元素都被计算一次。

于 2013-03-21T15:51:19.127 回答