一个列表转化为集合的时间复杂度是多少？

Question

我注意到了Python官网上集合操作的时间复杂度表格。但我只想问一下将列表转换为集合的时间复杂度是多少，例如：

在Python中，将列表转换为集合的时间复杂度为O(n)，其中n是列表中元素的数量。

l = [1, 2, 3, 4, 5]
s = set(l)

我有点了解这实际上是一个哈希表，但它是如何工作的呢？它的时间复杂度是O(n)吗？

- lxuechen

---

你可以测试一下...只需计时增加n的时间。(我不确定，但我猜应该是因为在哈希表中插入大多数情况下都是O(1)。)。 - Trilarion

谢谢，我想我只是太懒了，我应该习惯使用计时器模块。 - lxuechen

时间复杂度问题应该参考算法，而不是基于你的计算机上观察到的操作时间来回答。 - Jacob Lee

Answer 1

是的。遍历列表的时间复杂度为O(n)，将每个元素添加到哈希集合中的时间复杂度为O(1)，因此总操作的时间复杂度为O(n)。

- Mad Physicist

---

在最糟糕的情况下，如果每次都发生哈希碰撞，向哈希表中插入元素的时间复杂度为O(n)，总时间复杂度为O(n^2)，但幸运的是这种情况几乎不会发生。 - Trilarion

另外，如果您的内存管理或哈希分配非常糟糕，并且列表非常大，则性能不会达到O(n)。 - Mad Physicist

最坏情况似乎实际上是O(n^2)，当碰撞发生很多时。仅仅因为它可能不会发生并不意味着它改变了最坏情况。期望情况是O(n)。 - kiwicomb123

@kiwicomb123。这在注释中已经记录了。你建议在答案中做出哪些改变？ - Mad Physicist

当我们将列表转换为集合时，它也会对元素进行排序，那么这不就是O(n.logn)操作吗？ - Gopesh Khandelwal

@GopeshKhandelwal。它绝对不会对元素进行排序。您可能已经从过于短的输入中看到了一个巧合。集合是无序容器。 - Mad Physicist

Answer 2

在我的最后一次面试中，我被问到了同样的问题，但回答不正确。正如Trilarion在第一个解决方案中所评论的那样，最坏情况下的复杂度为O(n^2)。遍历列表需要O(n)，但是不能只将每个元素添加到哈希表中（集合是使用哈希表实现的）。在最坏的情况下，我们的哈希函数将每个元素哈希到相同的值，因此将每个元素添加到哈希集合中并非O(1)。这种情况下，我们需要将每个元素添加到链接列表中 - （请注意，哈希集合在冲突时有一个链接列表）。在添加到链表时，我们需要确保元素不存在（按定义，Set不包含重复项）。为了做到这一点，我们需要对于每个元素都遍历同一个链表，这将总共花费n*(n-1)/2 = O(n^2)的时间。

- Aven Desta