Python 的“输入”效率/速度如何？（时间复杂度明智）
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/12905513/
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
How efficient/fast is Python's 'in'? (Time Complexity wise)
提问by John
In Python, what is the efficiency of the inkeyword, such as in:
在Python中，in关键字的效率是多少，比如在：
a = [1, 2, 3]
if 4 in a:
...
采纳答案by Felix Kling
It depends on the right hand operand:
这取决于右手操作数：
The operators
inandnot intest for collection membership. [...] The collection membership test has traditionally been bound to sequences; an object is a member of a collection if the collection is a sequence and contains an element equal to that object. However, it make sense for many other object types to support membership tests without being a sequence. In particular, dictionaries (for keys) and sets support membership testing.
运算符
in和not in集合成员资格的测试。[...] 集合成员资格测试传统上与序列绑定；如果集合是一个序列并且包含等于该对象的元素，则该对象是该集合的成员。但是，许多其他对象类型支持成员资格测试而不是序列是有意义的。特别是，字典（用于键）和集合支持成员资格测试。
Classes can implement the special method __contains__to override the default behavior (iterating over the sequence) and thus can provide a more (or less) efficient way to test membership than comparing every element of the container.
类可以实现特殊的方法__contains__来覆盖默认行为（迭代序列），因此可以提供一种比比较容器的每个元素更（或更少）有效的方法来测试成员资格。
The membership test operators (
inandnot in) are normally implemented as an iteration through a sequence. However, container objects can supply the following special method with a more efficient implementation, which also does not require the object be a sequence.
成员资格测试运算符 (
in和not in) 通常实现为通过序列的迭代。但是，容器对象可以提供以下具有更高效实现的特殊方法，这也不需要对象是序列。
Since you have a list in your example, it is iterated over and each element is compared until a match is found or the list is exhausted. The time complexity is usually O(n).
由于您的示例中有一个列表，因此会对其进行迭代并比较每个元素，直到找到匹配项或列表用完为止。时间复杂度通常为O(n).
回答by Eduardo
The complexity for lists is:
列表的复杂性是：
O(n)
For sets it is:
对于集合，它是：
O(1)
