交叉口复杂度

Question

在Python中，您可以得到两个集合的交集：

>>> s1 = {1, 2, 3, 4, 5, 6, 7, 8, 9}
>>> s2 = {0, 3, 5, 6, 10}
>>> s1 & s2
set([3, 5, 6])
>>> s1.intersection(s2)
set([3, 5, 6])

有人知道这种相交（&）算法的复杂性吗？

编辑： 此外，有人知道Python集背后的数据结构是什么吗？

Answer 1

答案似乎是一个搜索引擎查询。您也可以使用此直接链接到python.org的“时间复杂性”页面。快速总结：

Average:     O(min(len(s), len(t))
Worst case:  O(len(s) * len(t))

编辑：正如雷蒙德在下面指出的那样，“最坏情况”的情况不太可能发生。我最初将其包括在内是为了彻底，我将其留给下面的讨论提供背景，但我认为Raymond是正确的。