python集合运算的时间复杂度？

问题描述：

用大 O表示法表示Python 的每个集合运算的时间复杂度是多少？

我正在使用 Python 的集合类型对大量项目进行操作。我想知道每个操作的性能将如何受到集合大小的影响。例如，添加和成员资格测试：

myset = set()
myset.add('foo')
'foo' in myset

谷歌搜索并没有找到任何资源，但似乎合理的是，Python 集合实现的时间复杂性应该得到仔细考虑。

如果它存在，那么提供类似链接就太好了。如果没有类似的东西，那么也许我们可以找到它？

找到所有集合运算的时间复杂度可获得额外分数。

解决方案 1：

根据Python wiki：时间复杂度，set实现为哈希表。因此，您可以预期平均在O(1)内进行查找/插入/删除。除非您的哈希表的负载因子太高，否则您会面临碰撞和 O(n)。

PS：由于某种原因，他们声称删除操作为 O（n），但这看起来像是输入错误。

PPS 对于 CPython 来说确实如此，pypy 则不同。

解决方案 2：

其他答案没有谈到集合上的两个关键操作：并集和交集。在最坏的情况下，并集将采用 O(n+m)，而交集将采用 O(min(x,y))，前提是集合中具有相同哈希值的元素不多。常见操作的时间复杂度列表可在此处找到：https://wiki.python.org/moin/TimeComplexity

解决方案 3：

该操作in应该与容器的大小无关，即O(1) ——给定一个最佳哈希函数。对于 Python 字符串来说，这应该几乎是正确的。对字符串进行哈希处理始终至关重要，Python 应该在这方面很聪明，因此您可以期待接近最佳的结果。

解决方案 4：

Python 中的集合类型基本上是作为 HashTable 实现的。

上面有很多很棒的答案，我只想指出一个遗漏的观点：

我认为还有一件事是哈希表的大小是预定义的，添加超出当前容量的元素会触发哈希表的大小调整。

对于复杂性部分（HashTable）：

摊销：

对于单个添加而言，其复杂度为 O(1)，因为调整大小并不频繁。

最坏情况：

O（n）调整大小涉及将所有元素重新散列到更大的表中，这是一个线性运算。