没有嵌套循环可能有二次时间复杂度吗？

Question

它进展得很顺利.我以为自己的时间复杂了.我正在尝试编码,并使用以下算法来解决他们的一个问题.我知道这个问题有更好的解决方案(置换检查) - 但我根本不明白没有嵌套循环的东西如何具有O(N ^ 2)的时间复杂度.我的印象是Javascript中的关联数组就像哈希并且非常快,并且不会被实现为耗时的循环.

这是示例代码

function solution(A) {
    // write your code in JavaScript (Node.js)
    var dict = {};

    for (var i=1; i<A.length+1; i++) {
        dict[i] = 1;
    }

    for (var j=0; j<A.length; j++) {
        delete dict[A[j]];
    }

    var keyslength = Object.keys(dict).length;
    return keyslength === 0 ? 1 : 0;
}

这是判决

Answer 1

他们的工具中必须存在一个您应该报告的错误:此代码具有复杂性O(n).相信我,我是互联网上的某个人.

在我的机器上:

console.time(1000);
solution(new Array(1000));
console.timeEnd(1000);
//about 0.4ms

console.time(10000);
solution(new Array(10000));
console.timeEnd(10000);
// about 4ms

更新:为了迂腐(原文如此),我仍然需要第三个数据点来表明它是线性的

console.time(100000);
solution(new Array(100000));
console.timeEnd(100000);
// about 45ms, well let's say 40ms, that is not a proof anyway