Intersection complexity

17 浏览
0 Comments

Intersection complexity

在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 set背后的数据结构是什么吗？（编辑：）

admin 更改状态以发布 2023年5月19日
0

2 答案

0 Comments

答案似乎可以通过 搜索引擎查询 得到。您也可以使用这个Python官方时间复杂度页面的直接链接。简单总结如下：

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

编辑：正如雷蒙德在下面指出的那样，“最坏情况”不太可能发生。我最初包括了它是为了全面，我保留它为了提供下面讨论的上下文，但我认为雷蒙德是正确的。

0
0 Comments

集合背后的数据结构是一个哈希表，典型的性能是摊销的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 result

0