问题描述
在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?
推荐答案
答案似乎是。您还可以使用。快速摘要:
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.
这篇关于交叉口复杂度的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持!