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

EN

您需要分配n个值，所以有那么多的工作要做。功随n的增加而线性增加。

尽管如此，您可以希望通过使用.fill来使代码更快一些。

const data: number[] = Array(n).fill(0);
data[someIndex] = someNumber;

但是不要弄错了，这仍然是O(n)：.fill可能更快，但是它仍然需要用零填充整个数组，这意味着需要初始化相应的内存大小，这样操作就具有线性时间复杂度。

但是，如果您放弃了需要分配零的要求，那么您只能存储someNumber。

const data: number[] = Array(n);
data[someIndex] = someNumber;

通过这种方式，您实际上不会为整个数组分配内存，因此此代码段将在恒定时间内运行。任何对与someIndex不同的索引的访问都会为您提供一个undefined值。你可以抓住这个条件，并将其转化为“零即时”：

let value = i in data ? data[i] : 0;

显然，如果要像这样访问数组的所有索引，则将再次具有线性时间复杂度。

根据实现细节，理论上可以在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)时间。如果有人在另一个浏览器(或其中一个浏览器的另一个版本)上得到不同的结果，请添加注释。