我注意到了Python官网上集合操作的时间复杂度表格。但我只想问一下将列表转换为集合的时间复杂度是多少,例如:
在Python中,将列表转换为集合的时间复杂度为O(n),其中n是列表中元素的数量。
l = [1, 2, 3, 4, 5]
s = set(l)
我有点了解这实际上是一个哈希表,但它是如何工作的呢?它的时间复杂度是O(n)吗?
我注意到了Python官网上集合操作的时间复杂度表格。但我只想问一下将列表转换为集合的时间复杂度是多少,例如:
在Python中,将列表转换为集合的时间复杂度为O(n),其中n是列表中元素的数量。
l = [1, 2, 3, 4, 5]
s = set(l)
我有点了解这实际上是一个哈希表,但它是如何工作的呢?它的时间复杂度是O(n)吗?
是的。遍历列表的时间复杂度为O(n)
,将每个元素添加到哈希集合中的时间复杂度为O(1)
,因此总操作的时间复杂度为O(n)
。
O(n^2)
。遍历列表需要O(n)
,但是不能只将每个元素添加到哈希表中(集合是使用哈希表实现的)。在最坏的情况下,我们的哈希函数将每个元素哈希到相同的值,因此将每个元素添加到哈希集合中并非O(1)。这种情况下,我们需要将每个元素添加到链接列表中 - (请注意,哈希集合在冲突时有一个链接列表)。在添加到链表时,我们需要确保元素不存在(按定义,Set不包含重复项)。为了做到这一点,我们需要对于每个元素都遍历同一个链表,这将总共花费n*(n-1)/2 = O(n^2)
的时间。