从列表中删除重复项的时间和空间复杂性

Question

我有下面的代码，我试图得到时间复杂度。

seen = set()
a=[4,4,4,3,3,2,1,1,1,5,5]
result = []
for item in a:
    if item not in seen:
        seen.add(item)
        result.append(item)
print (result)

据我所知，当我访问列表时，该操作的时间复杂度将是O(n)。与if块一样，每次我查找集合时，都会花费另一个O(n)。那么，总体时间复杂度是O(n^2)吗？set.add()是否也增加了复杂性？

另外，由于空间的复杂性，它是O(n)吗？因为集合的大小在每次遇到新元素时都会增加？

任何能够正确洞察时间和空间复杂性的输入或链接都是值得赞赏的。

Answer 1

Python中的集合被实现为哈希表(类似于字典)，因此in和set.add()都是O(1)。list.append()是also O(1)摊销的。

总之，这意味着由于a上的迭代，时间复杂度为O(n)。

空间复杂度也是O(n)，因为所需的最大空间与输入的大小成比例。

有关Python集合上各种操作的时间复杂性的有用参考，请参阅https://wiki.python.org/moin/TimeComplexity…Python The Mighty Dictionary对PyCon如何实现各种集合和字典操作的O(1)复杂度进行了有趣的深入研究。