如何描述以下代码的运行时分析？这是基数排序的第二步(第一步是创建计数器(。
const reAssignArraySlots = (arr, counter) => {
let i = 0;
let j = 0;
while(i<arr.length) {
let k = 0;
let num = counter[i] || 0;
while(k<num) {
arr[j] = i;
k+=1;
j+=1;
}
i+=1;
j+=1;
}
return arr;
};
我相信无论如何都会是O(n(，但我想检验一下这种直觉。示例：
A( 所有的元素都是一样的。计数器将为｛"2"：3｝。具有i的while循环将处理1x，具有k的while环路将处理3x，并且每个插入将是O(1(。我把3个插入加起来，形成O(3(，即O(n(
B( 所有元素都是独一无二的。计数器将为｛"2"：1、"1"：1和"3"：1｝。while循环将处理i 3x。每个插入将是O(1(，其将加起来为O(n(的O(3(。
C( 非唯一、非顺序元素。｛"4"：1，"1"：1、"3"：2｝。在这里我不确定。对于每个插入，我们都有O(1(，但对于i=2，我们有一个额外的检查，这不在这里。不确定这是否会使我们达到O(4(。最终，如果我们有足够稀疏的东西，这可以得到O(n^2(。
代码的其余部分：
const getCounter = (arr) => {
const counter = {};
let min, max;
arr.forEach((item) => {
if(counter[item] !== undefined) {
counter[item] += 1;
} else {
counter[item] = 1;
}
});
return counter;
};
export const countSort = (arr) => {
const counter = getCounter(arr);
return reAssignArraySlots(arr, counter);
};
我看到2个嵌套循环，所以我倾向于说它不比O(n^2(慢。
i在外循环中递增k在内部循环中递增(并在循环之前设置为零(j在两个循环中都递增
k对于每个循环可能不同，但假设有一个平均值ave_k
在循环结束时，在我看来j总是等于i * ave_k。
最大的问题是k(或ave_k(的大小是多少？
- 它与
i成正比吗？那么你就得到了O(n^2( - 它与
ln(i)成比例吗？那么你就得到了O(n ln(n(( - 它是常数，独立于
i吗？那么你就得到了O(n( - 它通常是
i的平方吗？那么你得到了O(n^2( - 它通常是
i的平方根吗？那么你得到了O(nsqrt(n((