python集操作的时间复杂性？

Question

Big O表示法中每个python设置操作的时间复杂度是多少？

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

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

谷歌搜索没有发现任何资源,但似乎合理的是,Python的集合实现的时间复杂性将被仔细考虑.

如果它存在,到一些链接像这将是巨大的.如果没有这样的东西,那么也许我们可以解决它？

用于查找所有设置操作的时间复杂度的额外标记.

Answer 1

根据Python维基:时间复杂度,set实现为哈希表.所以你可以期望在O(1)平均值中查找/插入/删除.除非您的哈希表的加载因子太高,否则您将面临冲突和O(n).

PS由于某种原因他们声称O(n)的删除操作看起来像一个错误的类型.

PPS这对CPython来说是真实的,pypy是另一回事.

Answer 2

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

Answer 3

操作in应独立于容器的大小，即 O（1） -给出最佳哈希函数 对于Python字符串，这应该几乎是正确的。散列字符串始终很关键，Python应该很聪明，因此您可以期待接近最佳的结果。