ChatGPT解决这个技术问题 Extra ChatGPT

python集合操作的时间复杂度?

Big O 表示法中,python 的每个集合操作的时间复杂度是多少?

我正在使用 Python 的 set type 对大量项目进行操作。我想知道每个操作的性能将如何受到集合大小的影响。例如,add 和成员资格测试:

myset = set()
myset.add('foo')
'foo' in myset

谷歌搜索并没有找到任何资源,但是仔细考虑 Python 的 set 实现的时间复杂度似乎是合理的。

如果它存在,指向类似 this 的链接会很棒。如果没有这样的东西,那么也许我们可以解决它?

用于查找所有集合操作的时间复杂度的额外标记。

虽然 GWW 的链接提供了非常丰富的信息,但您可以通过理解它们只是 python 字典的特殊情况(键,但没有值)来推断 python 集合的时间复杂度。所以,如果你知道哈希映射上操作的时间复杂度,你就差不多了。

S
Sergey Romanovsky

根据 Python wiki: Time complexityset 被实现为 hash table。因此,您可以期望在 O(1) 平均时间内查找/插入/删除。除非您的哈希表的负载因子太高,否则您将面临冲突和 O(n)。

PS出于某种原因,他们声称删除操作的时间为 O(n),这看起来像是输入错误。

PPS 这对于 CPython 来说是正确的,pypy 是一个 different story


在 python 中设置也可以进行自动排序。所以你认为插入新值仍然是 O(1) 时间复杂度
@thakurinbox 你能用链接支持你的陈述吗?
自动“排序”不排序。
@NareshThakur “在 python 中设置也可以自动排序。” - 不对。您可能刚刚观察到一个特殊情况。
t
towi

操作 in 应该独立于容器的大小,即。 O(1) -- 给定一个最优散列函数。对于 Python 字符串,这应该几乎为真。散列字符串总是至关重要的,Python 应该很聪明,因此您可以期待接近最佳的结果。


F
Fırat Kıyak

其他答案没有谈论集合上的两个关键操作:联合和交叉。在最坏的情况下,联合将采用 O(n+m) 而交集将采用 O(min(x,y)),前提是集合中具有相同哈希的元素不多。可以在此处找到常见操作的时间复杂度列表:https://wiki.python.org/moin/TimeComplexity


哇,这是一个非常有用的答案,它使我的代码加快了几个数量级,谢谢!