从列表中删除重复项的时间和 space 复杂度
Time and space complexity for removing duplicates from a list
我有以下代码，我正在尝试获取时间复杂度。
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() 是否也增加了复杂性？
此外，space 的复杂性是 O(n) 吗？因为每次遇到新元素集合的大小都会增加？
任何有助于正确了解时间和 space 复杂性的输入或链接都值得赞赏。
Python 中的集合被实现为哈希表（类似于字典），因此 in 和 set.add() 都是 O(1)。 list.append() 是 O(1) 摊销。
总而言之，这意味着时间复杂度为 O(n)，因为迭代 a。
Space 复杂度也是 O(n)，因为所需的最大值 space 与输入的大小成正比。
可以在 https://wiki.python.org/moin/TimeComplexity … and the PyCon talk The Mighty Dictionary 找到对 Python 集合的各种操作的时间复杂度的有用参考，它提供了对 Python 如何为各种操作实现 O(1) 复杂度的有趣研究set 和 dict 操作。
我有以下代码，我正在尝试获取时间复杂度。
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() 是否也增加了复杂性？
此外，space 的复杂性是 O(n) 吗？因为每次遇到新元素集合的大小都会增加？
任何有助于正确了解时间和 space 复杂性的输入或链接都值得赞赏。
Python 中的集合被实现为哈希表（类似于字典），因此 in 和 set.add() 都是 O(1)。 list.append() 是
总而言之，这意味着时间复杂度为 O(n)，因为迭代 a。
Space 复杂度也是 O(n)，因为所需的最大值 space 与输入的大小成正比。
可以在 https://wiki.python.org/moin/TimeComplexity … and the PyCon talk The Mighty Dictionary 找到对 Python 集合的各种操作的时间复杂度的有用参考，它提供了对 Python 如何为各种操作实现 O(1) 复杂度的有趣研究set 和 dict 操作。