javascript - 没有嵌套循环是否可能具有二次时间复杂度？

Question

一切顺利。我以为我对时间复杂度有所了解。我玩了一个关于 codility 的游戏，并使用以下算法解决了他们的一个问题。我知道这个问题有更好的解决方案(排列检查)——但我只是不明白没有嵌套循环的东西怎么会有 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

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

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