问创建长度为n的数组，在O(1)中用0初始化所有值(除了一个索引匹配某一条件外)？

EN

根据实现细节，理论上可以在O(1)时间内创建大小为n的数组--原则上，如果数组是作为哈希表实现的，则可以设置数组的length属性，而无需为其所有元素分配或初始化空间。ECMAScript规范用于Array(n)构造函数并不要求Array(n)做任何需要超过O(1)时间的事情，尽管它也没有要求时间复杂度为O(1)。

在实践中，Array(n)的时间复杂度取决于浏览器，尽管验证这一点有点棘手。performance.now()函数可以用来测量计算开始到结束之间的时间，但在许多浏览器中，该函数的精度被人为地降低，以防止像谱这样的CPU定时攻击。为了避免这种情况，我们可以调用构造器repetitions时间，然后除以repetitions经过的时间，以便更精确地测量每个构造函数调用。

我的计时代码如下：

function timeArray(n, repetitions=100000) {
    var startTime = performance.now();
    for(var i = 0; i < repetitions; ++i) {
        var arr = Array(n);
        arr[n-1] = 'foo';
    }
    var endTime = performance.now();
    return (endTime - startTime) / repetitions;
}

for(var n = 10000; n <= 1000000; n += 10000) {
    console.log(n, timeArray(n));
}

这是我来自Google Chrome (版本74)和Firefox (版本72)的结果；在Chrome上，性能很明显是O(n)，在Firefox上，很明显是O(1)，在我的机器上的时间相当一致，大约是0.01ms。

​

​

我用Chrome上的repetitions = 1000和火狐上的repetitions = 100000来测量，以便在合理的时间内得到足够准确的结果。

@M.Dietz在注释中提出的另一个选项是像var arr = [];一样声明数组，然后在某个索引(例如arr[n-1] = 'foo';)上赋值。结果显示，Chrome和Firefox都花了O(1)时间，这两个浏览器的运行时间都在1纳秒以下：

​

​

这表明使用[]的版本比使用Array(n)的版本要好，但规范仍然没有要求使用O(1)时间，因此可能会有其他浏览器需要O(n)时间。如果有人在另一个浏览器(或其中一个浏览器的另一个版本)上得到不同的结果，请添加注释。