交叉口复杂性

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

&谁知道这个intersection()算法的复杂性？

编辑:此外,有谁知道Python集背后的数据结构是什么？

Answer 1

的交集算法始终在运行O(分钟(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

[回答附加编辑中的问题]集合后面的数据结构是一个哈希表.

Answer 2

答案似乎是搜索引擎查询.您还可以使用此直接链接到python.org上的Time Complexity页面.快速摘要:

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

编辑:正如雷蒙德指出的那样,"最坏情况"的情况不太可能发生.我最初将它包括在内是彻底的,我将其留下来为下面的讨论提供背景,但我认为Raymond是对的.