Python的'in'效率/速度有多快？(明智的时间复杂性)

Question

在Python中,in关键字的效率是多少,例如:

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

Answer 1

列表的复杂性是:

O(n)

对于集合,它是:

O(1)

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

Answer 2

这取决于右手操作数:

运营商in和not in测试集合成员资格.[...]集合成员资格测试传统上与序列绑定; 如果集合是序列并且包含与该对象相等的元素,则对象是集合的成员.但是,许多其他对象类型支持成员资格测试而不是序列是有意义的.特别是,字典(用于键)和集支持成员资格测试.

类可以实现特殊方法__contains__来覆盖默认行为(迭代序列),因此可以提供更多(或更少)有效的方法来测试成员资格,而不是比较容器的每个元素.

成员资格测试运算符(in和not in)通常实现为序列的迭代.但是,容器对象可以使用更高效的实现提供以下特殊方法,这也不要求对象是序列.

由于您的示例中有一个列表,因此会对其进行迭代,并比较每个元素,直到找到匹配项或列表用尽为止.时间复杂度通常是O(n).