相交复杂度
相交复杂度
提问于 2011-11-12 04:07:15
在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])有人知道这个交集(&)算法的复杂性吗？
编辑:另外，有人知道集合背后的数据结构吗？
回答 3
Stack Overflow用户
回答已采纳
发布于 2011-11-12 04:13:58
答案似乎是搜索引擎查询。您也可以使用这个直接链接到python.org的时间复杂性页面。简短摘要：
Average: O(min(len(s), len(t))
Worst case: O(len(s) * len(t))编辑:正如雷蒙德所指出的，“最坏的情况”不太可能发生。我最初把它写得很透彻，我留下它是为了给下面的讨论提供背景，但我认为雷蒙德是对的。
Stack Overflow用户
发布于 2011-11-12 04:23:58
集合后面的数据结构是一个哈希表，其中典型的性能是摊销的O(1)查找和插入。
交点算法循环正好是min(len(s1), len(s2))时间。它每个循环执行一次查找，如果有匹配，则执行插入。在纯Python中，如下所示：
def intersection(self, other):
if len(self) <= len(other):
little, big = self, other
else:
little, big = other, self
result = set()
for elem in little:
if elem in big:
result.add(elem)
return resultStack Overflow用户
发布于 2017-01-25 18:01:00
两组大小的集合交集m,n可以通过以下方式与O(max{m,n} * log(min{m,n}))实现:假设m << n
1. Represent the two sets as list/array(something sortable)
2. Sort the **smaller** list/array (cost: m*logm)
3. Do until all elements in the bigger list has been checked:
3.1 Sort the next **m** items on the bigger list(cost: m*logm)
3.2 With a single pass compare the smaller list and the m items you just sorted and take the ones that appear in both of them(cost: m)
4. Return the new set步骤3中的循环将运行n/m迭代，每一次迭代都将使用O(m*logm)，因此对于m << n，您将具有O(nlogm)的时间复杂性。
我认为这是存在的最好的下界
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/8102478
复制相关文章
相似问题
腾讯云开发者
