JavaScript数组中的展开语法的时间复杂度是多少？

Question

我想知道在JavaScript中使用扩展运算符与数组的时间复杂度是多少。它是线性的O(n)还是常数的O(1)？

以下是语法示例：

let lar = Math.max(...nums)

- Jaaayz

---

我没有任何证据，但如果它不是O(n)，那就相当奇怪了。它必须遍历数组的每个元素。 - jhpratt

没有扩展运算符，只有扩展语法。;-) - RobG

@RobG，抱歉。我会编辑问题的 :) - Jaaayz

@jhpratt 嗯，至少能看到更清晰的画面，这就是我问的原因哈哈。 - Jaaayz

我认为这将取决于您想要进行比较的替代方案以及它正在运行的实现方式，例如在 OP 中与 Math.max.apply(null,nums) 进行比较，或者在主机对象与 Array.from(document.getElementsByTagName('p')) 或类似情况下进行比较。 - RobG

Answer 1

Spread调用对象的[Symbol.iterator]属性。对于数组，这将遍历数组中的每个项目，调用数组迭代器的.next()，直到迭代器耗尽，导致复杂度为O(N)。

出于完全相同的原因，for..of（也调用[Symbol.iterator]）循环也是O(N)：

const arr = [1, 2, 3];
for (const item of arr) {
  console.log(item);
}

查看以下代码片段，可以实时查看其执行需要一些时间：

const arr = new Array(3e7).fill(null);
const t0 = performance.now();
const arr2 = [...arr];
console.log(performance.now() - t0);

(如果操作是O(1)，那么它会几乎瞬间完成，但它并不是。)

参数展开与数组展开不同，但它使用相同的操作（迭代可迭代对象直到耗尽），因此具有相同的复杂度。

For function calls:

myFunction(...iterableObj);

- CertainPerformance

---

只是注意到，像上面这样的简单性能测试很可能受不同实现如何优化代码的影响。对正在执行的操作进行更改可能会对相对性能产生重大影响，超出了在 ...、for..in、for..of 等方面的任何差异。 :-) - RobG