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

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

更新：迂腐（原文如此），我还需要第三个数据点来证明它是线性的

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

Answer 2

是否可以在没有嵌套循环的情况下实现二次时间复杂度？是的。考虑一下：

function getTheLengthOfAListSquared(list) {
   for (var i = 0; i < list.length * list.length; i++) { }
   return i;
}

至于那个特定的代码示例，它似乎确实像@floribon 所说的那样是 O(n)，因为 Javascript 对象查找应该是常数时间。

请记住，制作一个采用任意函数并确定该函数是否会完成完全的算法显然是不可能的 (halting problem)，更不用说确定复杂性了。编写一个工具来静态确定除最简单程序以外的任何东西的复杂性将非常困难，该工具的结果证明了这一点。

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

Is it possible to have quadratic time complexity without nested loops?

javascript

complexity-theory

time-complexity