python集合操作的时间复杂度? [英] Time complexity of python set operations?

问题描述

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

What is the the time complexity of each of python's set operations in Big O notation?

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

I am using Python's set type for an operation on a large number of items. I want to know how each operation's performance will be affected by the size of the set. For example, add, and the test for membership:

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

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

Googling around hasn't turned up any resources, but it seems reasonable that the time complexity for Python's set implementation would have been carefully considered.

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

If it exists, a link to something like this would be great. If nothing like this is out there, then perhaps we can work it out?

找到所有集合操作的时间复杂度的额外标记.

Extra marks for finding the time complexity of all set operations.

推荐答案

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

According to Python wiki: Time complexity, set is implemented as a hash table. So you can expect to lookup/insert/delete in O(1) average. Unless your hash table's load factor is too high, then you face collisions and O(n).

附言出于某种原因，他们声称 O(n) 用于删除操作，这看起来像是一个错误类型.

P.S. for some reason they claim O(n) for delete operation which looks like a mistype.

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

P.P.S. This is true for CPython, pypy is a different story.

这篇关于python集合操作的时间复杂度?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！