交叉口复杂度 [英] Intersection complexity

问题描述

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

In Python you can get the intersection of two sets doing:

>>> 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])

任何人知道这个交集（& ）算法的复杂性吗？

Anybody knows the complexity of this intersection (&) algorithm?

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

In addition, does anyone know what is the data structure behind a Python set?

推荐答案

答案似乎是搜索引擎查询消失。您还可以使用直接链接到位于python.org的时间复杂度页面。快速摘要：

The answer appears to be a search engine query away. You can also use this direct link to the Time Complexity page at python.org. Quick summary:

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

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

As Raymond points out below, the "worst case" scenario isn't likely to occur. I included it originally to be thorough, and I'm leaving it to provide context for the discussion below, but I think Raymond's right.

这篇关于交叉口复杂度的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！