Python的“in”有多快/多快? (时间复杂性明智)

在Python中, in关键字的效率如何:

 a = [1, 2, 3] if 4 in a: ... 

这取决于右手操作数 :

运营商innot intesting收集成员资格。 […]集合成员资格testing传统上被绑定到序列; 如果集合是一个序列并且包含一个等于该对象的元素,则对象是集合的成员。 但是,对于许多其他对象types来说,支持成员testing而不是序列是有意义的。 特别是,字典(键)和集支持会员资格testing。

类可以实现特殊的方法__contains__来覆盖默认的行为(遍历序列),因此可以提供一个更多(或更less)有效的方法来testing成员资格,而不是比较容器的每个元素。

成员testing操作符( innot in )通常是通过一个序列迭代来实现的。 但是,容器对象可以提供更高效的实现,下面的特殊方法也不需要该对象是一个序列。


既然你在你的例子中有一个列表,它将被迭代,每个元素都会被比较,直到find匹配或者列表被用尽。 时间复杂度通常是O(n)

列表的复杂性是:

 O(n) 

对于集合它是:

 O(1) 

http://wiki.python.org/moin/TimeComplexity