algorithm - 计数排序的运行时间

我试图了解计数排序的运行时间。在我的笔记中，它说，假设数组 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
         }
  }

我不明白为什么这个总和等于 n。外循环迭代k次，内循环最多迭代n次，所以一定是O(nk)。有人可以解释一下吗？谢谢

最佳答案

正如你所看到的循环

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 ，因为每个元素都被计数一次。

关于algorithm - 计数排序的运行时间，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/15546979/