將列表轉換爲在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是列表的長度。

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