将列表转换为在Python中设置的运行时间

Question

在Python中，如果将列表转换为集合，那么运行时间和空间的复杂性如何？

Example: 
data = [1,2,3,4,5,5,5,5,6] 

# this turns list to set and overwrites the list 
data = set(data) 

print data 
# output will be (1,2,3,4,5,6) 

Answer 1

将列表转换为集合需要访问列表中的每个项目O（n）。将一个元素插入到集合中是O（1），因此总体时间复杂度将是O（n）。

新组所需的空间小于或等于列表的长度，因此也是O（n）。

这是Python数据结构的一个很好的reference。

Answer 2

你必须通过整个列表，这是O（n）的时间进行迭代，然后将每个插入到一组，它是O（1）时间。所以总的时间复杂度是O（n），其中n是列表的长度。

除了正在创建的集合或正在使用的列表之外，不需要其他空间。