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

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

您需要分配 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;

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

Answer 2

在 O(1) 时间内创建大小为 n 的数组在理论上是可行的，具体取决于实现细节 - 原则上，如果数组实现为哈希表，则其 length 属性可以在不为其所有元素分配或初始化 space 的情况下设置。 Array(n) 构造函数的 ECMAScript specification 并不强制要求 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.01 毫秒。

我在 Chrome 上使用 repetitions = 1000 进行测量，在 Firefox 上使用 repetitions = 100000 进行测量，以便在合理的时间内获得足够准确的结果。

@M.Dietz 在评论中提出的另一个选项是像 var arr = []; 一样声明数组，然后在某个索引处赋值（例如 arr[n-1] = 'foo';）。事实证明，在 Chrome 和 Firefox 上都需要 O(1) 时间，两者始终在一纳秒以下：

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

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

Create array with length n, initialize all values with 0 besides one which index matches a certain condition, in O(1)?

javascript

algorithm

complexity-theory

typescript