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

标签 python time-complexity

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

这样的表达式需要多少时间(渐近地讲)
{1,2}=={2,1}

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

最佳答案

集合之间的比较由 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;

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

关于python - 在 Python 中检查两个集合是否相等的时间复杂度,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/12390298/

相关文章:

python - 检查numpy数组是否连续?

java - 数组中的元素,使得其左侧元素的总和等于其右侧元素的总和

算法分析 : Big Oh Complexity, 将输出表示为一个函数

algorithm - 堆排序的目的是什么?

sorting - Bogosort 的平均时间复杂度是多少?

python - Moviepy 制作两个 concatenate_videoclip 的 CompositeVideoClip

python - 使用 try/except 处理多个绘图

python - 从字典的字典创建 python 数组

c++ - std::vector 实现是否使用内部数组或链表或其他?

python - 在同一对象上多处理独立函数的最有效方法