Python中集差函数的运行时间是多少？

Question

这个问题解释了它，但是Python中的集差运算的时间复杂度是多少？

前任：

A = set([...])
B = set([...])

print(A.difference(B)) # What is the time complexity of the difference function? 

我的直觉告诉我，O(n)因为我们可以遍历集合 A 并且对于每个元素，查看它是否在恒定时间内（使用哈希函数）包含在集合 B 中。

我对吗？

（这是我遇到的答案：https : //wiki.python.org/moin/TimeComplexity）

Answer 1

看起来你是对的，O(n)在最好的情况下，差异是复杂的

但请记住，在最坏的情况下（最大化与散列的冲突），它可以提升到O(n**2)（因为查找最坏的情况是O(n)：set()是如何实现的？但似乎您通常可以依赖O(1)）

顺便说一句，速度取决于set. 整数散列很好（大致和它们自己一样，可能有一些模数），而字符串需要更多的 CPU。