Python中*in*运算符的复杂性
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/13884177/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Complexity of *in* operator in Python
提问by Sajad Rastegar
What is the complexity of the inoperator in Python? Is it theta(n)?
Python 中in运算符的复杂性是什么？是 theta(n) 吗？
Is it the same as the following?
和下面的一样吗？
def find(L, x)
for e in L:
if e == x:
return True
return False
L is a list.
L 是一个列表。
采纳答案by Andrew Clark
The complexity of independs entirely on what Lis. e in Lwill become L.__contains__(e).
的复杂性in完全取决于是什么L。e in L将成为L.__contains__(e).
See this time complexity documentfor the complexity of several built-in types.
有关几种内置类型的复杂性，请参阅此时间复杂度文档。
Here is the summary for in:
这里是总结in：
- list - Average: O(n)
- set/dict - Average: O(1), Worst: O(n)
- 列表 - 平均值：O(n)
- set/dict - 平均：O(1)，最差：O(n)
The O(n) worst case for sets and dicts is very uncommon, but it can happen if __hash__is implemented poorly. This only happens if everything in your set has the same hash value.
集合和字典的 O(n) 最坏情况非常罕见，但如果__hash__实施不当，则可能会发生。仅当您的集合中的所有内容都具有相同的哈希值时才会发生这种情况。
回答by kindall
It depends entirely on the type of the container. Hashing containers (dict, set) use the hash and are essentially O(1). Typical sequences (list, tuple) are implemented as you guess and are O(n). Trees would be average O(log n). And so on. Each of these types would have an appropriate __contains__method with its big-O characteristics.
这完全取决于容器的类型。散列容器 ( dict, set) 使用散列并且本质上是 O(1)。典型的序列 ( list, tuple) 是按照您的猜测实现的，并且是 O(n)。树将是平均 O(log n)。等等。这些类型中的每一种都有一个__contains__具有大 O 特征的适当方法。
回答by Marcin
It depends on the container you're testing. It's usually what you'd expect - linear for ordered datastructures, constant for the unordered. Of course, there are both types (ordered or unordered) which might be backed by some variant of a tree.
这取决于您正在测试的容器。这通常是您所期望的 - 有序数据结构的线性，无序的常量。当然，有两种类型（有序或无序）可能由树的某些变体支持。
