JavaScript Set：两种创建方式的时间与空间复杂度分别是什么？

结论先行 #

两种创建Set的方式，时间复杂度和空间复杂度完全一致：

• 时间复杂度：O(n)，其中n为输入数组nElementsArray的长度
• 空间复杂度：O(k)，其中k为数组中唯一元素的数量（最坏情况k=n，最好情况k=1）

详细解释 #

时间复杂度

不管是通过构造函数直接传入数组，还是手动循环调用Set.prototype.add()，本质都是遍历数组中的每一个元素，再将元素插入Set集合中。

JavaScript的Set基于哈希表实现，单个元素的插入操作平均时间复杂度为O(1)。遍历n个元素加上n次O(1)的插入，整体时间复杂度就是O(n)。

空间复杂度

Set的核心作用是存储唯一元素，所以最终占用的空间取决于数组中不重复元素的数量k：

• 如果数组中所有元素都唯一（最坏情况），空间复杂度为O(n)
• 如果数组中所有元素都重复（最好情况），空间复杂度为O(1)

两种方式最终生成的Set内容完全相同，因此空间消耗也一致。

内容的提问来源于stack exchange，提问作者Salitha