python - 从列表中删除重复项的时间和空间复杂度

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 block 一样，这将花费另一个 O(n)。那么整体时间复杂度是O(n^2)吗？ set.add() 是否也增加了复杂性？

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

欢迎提供任何有助于正确了解时空复杂性的输入或链接。

Answer 1

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

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

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

可以在 https://wiki.python.org/moin/TimeComplexity 找到对 Python 集合的各种操作的时间复杂度的有用引用。 ...和 ​​PyCon 谈话 The Mighty Dictionary提供了对 Python 如何为各种集合和字典操作实现 O(1) 复杂度的有趣研究。