python - 在 Python 中检查两个集合是否相等的时间复杂度

Question

阅读 this question ，我想知道 Python 计算像

这样的表达式需要多少时间(渐近地讲)

{1,2}=={2,1}

也就是说，检查 set class 的两个实例是平等的。

Answer 1

集合之间的比较由 function set_richcompare in setobject.c, line 1848 实现.您会看到相等性的实现如下:

1. 如果集合的大小不同，则返回 false。

2. 如果两个集合都经过哈希处理，并且哈希值不同，则返回 false。

3. 调用set_issubset .

两个集合的子集测试如下所示:

while (set_next(so, &pos, &entry)) {
    int rv = set_contains_entry((PySetObject *)other, entry);
    if (rv == -1)
        return NULL;
    if (!rv)
        Py_RETURN_FALSE;
}
Py_RETURN_TRUE;

您会发现它的工作原理是遍历第一组的所有元素，然后在另一组中查找每个元素。所以(除非有很多散列冲突)这与第一组的大小成线性关系。