Array.from的时间复杂度

Question

Array.from() 的时间复杂度是什么？例如：

const set = new Set();
set.add('car');
set.add('cat');
set.add('dog');

console.log(Array.from(set)); // time complexity of making this convertion from Set to Array

- Shota

---

仅迭代成本加上推送到数组的成本（对结果长度为O(n)），因此Set的时间复杂度为O(n)。 - Ry-

你为什么问呢？Array.from()有一个不同的“问题”；与其他创建该数组的方法相比，它非常慢。这似乎是由于该方法可能需要处理各种输入类型而产生的开销所致。因此，对于小型数据结构，这种开销可能会超过实际任务的执行时间。 - Thomas

分享这个可能对某些人有用，我们也可以像这样返回数组 const newArr = [...new Set(arr)]; 不需要总是写 Array.from(set)。 - Gorakh Nath

Answer 1

这是一个 O(n) 的操作。当应用于可迭代对象（例如一个 Set），Array.from 迭代该可迭代对象，并将每个返回的元素放入新数组中，因此对于可迭代对象返回的每个元素都会进行一次操作。

- CertainPerformance

---

这并不一定意味着它是 O(n)。时间复杂度取决于内部实现，因此如果内部使用类似 Array.prototype.push 的方法向返回的数组添加元素，则可能是 O(n log n)。虽然这是一种愚蠢的实现方式，但在我看到其他情况之前，我会假设最坏的情况。这也可以解释为什么它运行得如此缓慢。 - PHP Guru

就我个人而言，我认为当数据量足够大以至于复杂性开始表现出可见效应时，各种现代 JS 引擎的编写者并不会选择使用愚蠢低效的算法。虽然理论上某人可以采用这种算法，但这将是一个非常奇怪的决定（除非涉及奇怪的边缘情况，在这种情况下，所有的赌注都无所谓）。 - CertainPerformance

我现在相当确定时间复杂度确实是O(n log n)，因为我进行了基准测试，使用Array.from() 并没有比仅创建大小为0的数组然后调用Array.prototype.push 1600万次更快。希望JavaScript未来的版本能够解决这个问题。 - PHP Guru

Answer 2

迭代次数与集合元素数量成正比，因此时间复杂度始终为O(n)。实际时间复杂度为从集合中检索值的O(n)，将值推入数组的O(n)。

O(n) + O(n) = O(2n)

但是，由于我们在计算时没有考虑常数值，因此使用 n 值进行计算应为 O(n)。

- Amit