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/

相关文章:

mysql - 在主键上搜索时从 MySQL 数据库中获取一行的时间复杂度是多少?

python - 用于捕获 HTML 源代码中花括号之间所有内容的正则表达式

python - 用 ModelChoiceField 替换 ManyToMany-Relation

python - 如何修改Python日志记录工具的行为?

time-complexity - for循环中递归的时间复杂度

lisp - cdr的时间分析

python - 仅从字典中获取特定值

python - python 新手从文件创建两个字典需要特定行

C++ - std::unordered_map <int,int> 中的最坏情况和平均情况插入时间复杂度?

algorithm - 大O : How to determine runtime for a for loop incrementation based on outer for loop?