交集复杂度

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 集合背后的数据结构是什么吗？

- juliomalegria

Answer 1

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

- Raymond Hettinger

---

根据我上面链接的维基百科，你代码中 elem in big 的最坏情况是 O(n)（当然平均情况是 O(1)）。这就是交集最坏情况为 O(len(s)*len(t)) 的基础。你有什么想法吗？ - Kurt McKee

“最坏情况”假设数据不适合用于dict和set中使用的哈希表。数据必须是每个数据具有完全相同的哈希值，这将强制哈希表执行类似于线性搜索的操作来执行__contains__检查。换句话说，我完全不用担心这个问题。集合交集是盲目快速的 - 它甚至重复使用内部存储的哈希值，因此不需要进行任何*hash()*调用。 - Raymond Hettinger

3.x 代码链接：这里，适用于3.9版本。 - user650654

交集算法并不总是以所述的复杂度运行，正如@RaymondHettinger在评论中承认的那样。在实践中，这可能并不重要，但请注意，从理论上讲，这个答案是不正确的。 - apeman

@lusil，那是非常误导人的说法。这就像说赌徒可以在轮盘赌上每次都赢一样。虽然哈希表是一种概率算法，但是用户的胜率非常高。如果给定一个大表和一个随机的哈希函数，交集算法“失败”的可能性是微乎其微的，几乎不可能发生。 - Raymond Hettinger

我更喜欢当前的措辞！ - apeman

Answer 2

答案似乎只需进行搜索引擎查询。您也可以使用这个到python.org的时间复杂度页面的直接链接。快速摘要：

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

编辑：正如下面Raymond所指出的，"最坏情况"不太可能发生。我最初包括它是为了全面，现在我认为Raymond是正确的，但为了提供下面讨论的背景，我将保留它。

- Kurt McKee

---

那是个很糟糕的最坏情况，不是吗？ - juliomalegria

它看起来不像是先使用排序（这需要对象具有排序），而是只是进行“哈希探测”：可能为了更好的 C 和平均值（且没有排序要求）。据我所知，最大所需复杂度为 O(n log n) + O(n)，其中包括排序。然而，Big-O是一个上限，并且还有实际考虑因素… - user166390

我认为这里的主要问题是集合是一个无序集合。在C++中，您可以使用2 *（L1 + L2）-1的时间复杂度对两个排序列表进行交集运算。这是一个非常好的复杂度！http://cplusplus.com/reference/algorithm/set_intersection/ - juliomalegria

这个答案在“最坏情况”时间方面有些误导性。不要让它让你远离一个完全良好的算法。 - Raymond Hettinger

@user124384 很有趣，第一个搜索结果是来自该超链接的这个帖子。 - THIS USER NEEDS HELP

Answer 3

两个大小为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

第三步中的循环将运行 n/m 次迭代，每次迭代需要 O(m*logm) 的时间，因此对于 m << n，您将具有 O(nlogm) 的时间复杂度。

我认为这是存在的最佳下限。

- Elad Yehezkel