javascript - 创建长度为 n 的数组，除了索引符​​合特定条件的值之外，将所有值初始化为 0，时间复杂度为 O(1)？

Question

我想创建一个长度为 n 的数字类型数组。除了索引与条件匹配的值外，数组内的所有值都应为 0。

这就是我目前的做法:

const data: number[] = [];
for (let i = 0; i < n; i++) {
  if (i === someIndex) {
    data.push(someNumber);
  } else {
    data.push(0);
  }
}

因此，假设 n = 4、someIndex = 2、someNumber = 4 将生成数组 [0, 0 , 4, 0].

有没有办法在 O(1) 而不是 O(n) 内完成它？

Answer 1

在 O(1) 时间内创建大小为 n 的数组理论上是可能的，具体取决于实现细节 - 原则上，如果数组实现为哈希表，则其长度 可以设置属性，而无需为其所有元素分配或初始化空间。 ECMAScript specification对于 Array(n) 构造函数并不强制要求 Array(n) 应该执行任何需要超过 O(1) 时间的操作，尽管它也没有要求要求时间复杂度为O(1)。

实际上，Array(n) 的时间复杂度取决于浏览器，尽管验证这一点有点棘手。 performance.now()函数可用于测量计算开始和结束之间耗时，但在许多浏览器中该函数的精度被人为降低，以防止像 Spectre 这样的 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 和在 Firefox 上使用 repetitions = 100000 进行测量，以便在合理的时间内获得足够准确的结果。

@M.Dietz 在评论中提出的另一个选项是像 var arr = []; 一样声明数组，然后在某个索引处分配(例如 arr[n-1] ='foo';)。事实证明，这在 Chrome 和 Firefox 上都需要 O(1) 时间，并且始终低于 1 纳秒:

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