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

问题描述

在 Big O 符号中每个python的集合操作的时间复杂度是多少？

我正在使用Python的设置类型对大量物品进行操作。我想知道每个操作的性能如何受到该组的大小的影响。例如，添加以及成员资格测试：

  myset = set（）
 myset.add（'foo'）
'foo'在myset 
  

Google搜索引擎没有提供任何资源，但是很明显，Python集合实现的时间复杂度已经被仔细考虑了。 p>

如果存在，则链接到像这个这样的东西会很棒。如果没有这样的话，那么也许我们可以解决这个问题？

查找所有设置操作的时间复杂度的额外标记。

解决方案

中的操作应该与容器的大小无关，即给出了一个最优的哈希函数O（1）。对于Python字符串，这应该是几乎。哈希字符串总是至关重要的，Python应该很聪明，因此您可以预期接近最佳结果。

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

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

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.

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.

解决方案

The operation in should be independent from he size of the container, ie. O(1) -- given an optimal hash function. This should be nearly true for Python strings. Hashing strings is always critical, Python should be clever there and thus you can expect near-optimal results.

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