python - 路口复杂度

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

有人知道这个交集(&)算法的复杂度吗？

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

Answer 1

集合背后的数据结构是一个hash table其中典型性能是分摊的 O(1) 查找和插入。

intersection algorithm精确地循环 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