Python集操作的时间复杂度？

Question

在Big O表示法中每个Python集合操作的时间复杂度是多少？

我使用Python的set type进行大量项目的操作。我想知道每个操作的性能如何受设置大小的影响。例如，add，并在成员测试：

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

周围的Googling还没有打开任何资源，但它似乎是合理的，对于Python的一套执行的时间复杂度会被慎重考虑。

如果存在，像this这样的链接会很好。如果没有这样的事情，那么我们可以解决这个问题吗？

用于查找时间复杂度的额外标记全部设置操作。

Answer 1

操作in应该独立于他的容器大小，即。 O（1） - 给定最佳散列函数。对于Python字符串，这应该是近。散列字符串总是至关重要的，Python应该很聪明，因此您可以期待近乎最佳的结果。

Answer 2

根据Python wiki: Time complexity,集合实现为hash table。因此，您可以期望在O（1）平均值中查找/插入/删除。除非你的哈希表的加载因子太高，否则你面对碰撞和O（n）。

P.S.由于某种原因，他们声称O（n）是删除操作，看起来像是一个错误类型。

P.P.S. CPython是这样，pypy是different story。