python - 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): How is set() implemented? ，但似乎你通常可以依赖 O(1))

顺便说一句，速度取决于集合中对象的类型。整数很好地散列(大致与它们本身一样，可能有一些模数)，而字符串需要更多的 CPU。