我注意到python官方网站上的集合操作的时间复杂性表。但我只想问，将列表转换为集合的时间复杂度是多少，例如
l = [1, 2, 3, 4, 5]
s = set(l)
我知道这实际上是一个哈希表，但它到底是如何工作的？那么它是O（n）吗？
是。对列表进行迭代是O(n)，将每个元素添加到哈希集是O(1)，因此总操作是O(n)。
在上次面试中，我被问到了同样的问题，但没有答对。正如Trilarion在第一个解决方案中所评论的，最坏情况下的复杂性是O(n^2)。遍历列表需要O(n)，但不能只将每个元素添加到哈希表中（集合是使用哈希表实现的）。在最坏的情况下，我们的哈希函数会将每个元素哈希为相同的值，因此将每个元素添加到哈希集不是O（1）。在这种情况下，我们需要将每个元素添加到一个链表中-（注意，哈希集在发生冲突时有一个链表）。当添加到链表时，我们需要确保元素不存在（因为Set by definition没有重复项）。为此，我们需要对每个元素的相同链表进行迭代，总共需要n*(n-1)/2 = O(n^2)。