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

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和{}都是O（1）。list.append()为{a1}O（1）摊销。在

总之，这意味着时间复杂度是O（n），这是由于a上的迭代。在

空间复杂性也是O（n），因为所需的最大空间与输入的大小成正比。在

关于Python集合上各种操作的时间复杂性，可以在https://wiki.python.org/moin/TimeComplexity上找到一个有用的参考资料，PyCon的谈话The Mighty Dictionary提供了一个有趣的研究，探讨Python如何为各种set和dict操作实现O（1）复杂性。在