将列表转换为在Python中设置的运行时间
问题描述:
在Python中,如果将列表转换为集合,那么运行时间和空间的复杂性如何?将列表转换为在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)
答
将列表转换为集合需要访问列表中的每个项目O(n)。将一个元素插入到集合中是O(1),因此总体时间复杂度将是O(n)。
新组所需的空间小于或等于列表的长度,因此也是O(n)。
这是Python数据结构的一个很好的reference。
答
你必须通过整个列表,这是O(n)的时间进行迭代,然后将每个插入到一组,它是O(1)时间。所以总的时间复杂度是O(n),其中n是列表的长度。
除了正在创建的集合或正在使用的列表之外,不需要其他空间。