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

问题描述 投票:0回答:3

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

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

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

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

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

发现 all 集合操作的时间复杂度的额外分数。

python data-structures set complexity-theory big-o
3个回答
144
投票

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

附言出于某种原因,他们声称删除操作的时间复杂度为 O(n),这看起来像是打错字了。

P.P.S.这对 CPython 来说是正确的,pypy 是一个不同的故事.


18
投票

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


12
投票

操作

in
应该独立于容器的大小,即。 O(1)——给定一个最优哈希函数。对于 Python 字符串,这应该是 nearly true。哈希字符串总是很关键,Python 在这方面应该很聪明,因此您可以期待接近最佳的结果。

© www.soinside.com 2019 - 2024. All rights reserved.