我希望你能帮我翻译计数排序的运行时间。在我的笔记中,它说假设数组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)。有人可以解释一下吗?谢谢
times
,很明显最内层循环总共最多只会执行n
次,而不是nk
次。 - Bernhard Barker