Python 集操作的时间复杂度？

在大 O表示法中，每个 python 的 set 操作的时间复杂度是多少？

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

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

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

如果它存在，链接到类似这个的东西将是伟大的。如果外面没有这样的东西，也许我们可以解决它？

用于查找所有集合操作的时间复杂性的额外标记。

168453 次浏览

小开

操作 in应该独立于容器的大小，即。O (1)——给定一个最佳散列函数。对于 Python 字符串，这应该是 差不多真。散列字符串总是很关键的，Python 在这方面应该很聪明，因此你可以期待接近最优的结果。

小开

根据 Python wiki: 时间复杂性，准备好了实现为哈希表。因此，可以期望在 O (1)平均值中查找/插入/删除。除非散列表的负载因子太高，否则将面临冲突和 O (n)。

另外，由于某种原因，他们声称 O (n)为删除操作，这看起来像一个错误的类型。

另外，对于 CPython 来说是这样的，pypy 是那就另当别论了。

小开

其他的答案没有提到集合上的两个关键操作: 联合和交叉。在最坏的情况下，联合将采用 O (n + m) ，而交会将采用 O (min (x，y)) ，前提是在具有相同散列的集合中没有多少元素。常见操作的时间复杂性列表可以在这里找到: https://wiki.python.org/moin/TimeComplexity