多集合交集操作的平均复杂度及其底层实现方式

Question

多集合交集操作的平均复杂度及其底层实现方式

pythonpython-3.xalgorithmdata-structuresset

3

Python维基上没有提及多集合交集的平均复杂度：

https://wiki.python.org/moin/TimeComplexity

只给出了最坏情况的复杂度：

(n-1)*O(l) where l is max(len(s1),..,len(sn))

多集合交集操作的平均复杂度是多少？这个操作在底层是如何实现的？

set.intersection(s1,s2,s2,s4 ...sn)

在Python-wiki中，因为它们的最坏情况复杂度不同，多集合交集操作是否以与两个集合交集操作不同的方式实现：

2个集合的交集: O(len(s) * len(t)) 多个集合的交集: (n-1)*O(l)，其中l是max(len(s1),..,len(sn))

因此，使用多集合公式的两个集合的复杂度应该是:

--> (2-1)*O(l) where l is max(len(s1), len(s2)`
--> O(max(len(s1), len(s2))

我认为它与两个集合交集操作的复杂度符号表示相当不同。

顺便说一下，除了使用集合交集进行不同集合之间的成员检查外，是否有更好的方法？

注意：我希望得到的是解释而不仅仅是复杂度O()符号表示 :)

- utengr

2个回答

阿里云服务器只需要99元/年，新老用户同享，点击查看详情

2

这个方法的基础C实现在CPython源代码中，负责多个集合交集的部分被称为set_intersection_multi。下面是代码：

set_intersection_multi(PySetObject *so, PyObject *args)
{
    Py_ssize_t i;
    PyObject *result = (PyObject *)so;

    if (PyTuple_GET_SIZE(args) == 0)
        return set_copy(so);

    Py_INCREF(so);
    for (i=0 ; i<PyTuple_GET_SIZE(args) ; i++) {
        PyObject *other = PyTuple_GET_ITEM(args, i);
        PyObject *newresult = set_intersection((PySetObject *)result, other);
        if (newresult == NULL) {
            Py_DECREF(result);
            return NULL;
        }
        Py_DECREF(result);
        result = newresult;
    }
    return result;
}

正文：

如您所见，它正在循环遍历传递给调用者的参数（Python对象），并尝试计算预期 set 与所有其他传递的对象的交集。

在 Python 的维基中提到的最坏情况是完全合理的。由于两个集合 s 和 t 之间的交集的复杂度为 O(len(s) * len(t))，因此在创建多个集合（s1&s2&..&sn）的交集时，最坏情况发生在所有集合都有效且包含项的情况下，并且循环执行 N - 1 次^*。

这意味着它在所有集合之间执行 n-1 个单一的交集计算，而在计算大 O 表示法时，我们应该只考虑最大长度。因此，它的复杂度为 (n-1)*O(l)，其中 l 是 max(len(s1),..,len(sn))。

此外，如果你想更好地理解两个集合或一个集合和另一个可迭代对象之间的交集复杂度（因为你可以执行类似于 set(x).intersection(list(y)) 的操作），其时间复杂度为 O(len(s) * len(t))，我强烈建议你仔细查看 set_intersection 函数的源代码。

第一个参数在循环之前被复制到PyObject *result中。

- Mazdak

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，

- Graipher · Accepted Answer

如在一个类似的问题中已经回答（As already answered），计算两个集合的交集实现方式是类比于（analogous to）：

def intersect(a, b):
    if len(a) > len(b):
        a, b = b, a

    c = set()
    for x in a:
        if x in b:
            c.add(x)
    return c

对于多个集合，它被实现为一系列成对交集的链，大致相当于：

def intersect_multi(a, *others):
    result = a.copy()
    for other in others:
        newresult = result.intersect(other)
        if not newresult:
            return set()
    result = newresult

平均复杂度可能没有给出，因为它取决于此函数是否在遍历所有"others"之前返回，这是由于交集为空导致的。因此，它的复杂度可以在O(k)和最坏情况之间任何位置，其中k是"others"中第一个集合的长度。因此，该函数的最坏情况复杂度为(N-1)*max(O(set_intersection))。O(set_intersection)通常为O(min(k, l))，如您所指出，但如果第二个集合不是一个集合，则为O(max(k, l))。我想这在此处已经包含了，因此基本上由最长的集合确定。维基百科中关于O(set_intersection)的最坏情况很少发生，正如Raymond Hettinger在此帖子中所指出的那样。显然，它仅在每次都有哈希冲突的情况下才会发生，因此if x in b将成为O(n)（其最坏情况复杂度）。似乎这种最坏情况并没有包含在多个集合交集的最坏情况复杂度中（也许是因为所有集合成员发生哈希冲突的可能性非常小？）。