Python的“输入”效率/速度如何？（时间复杂度明智）

Question

在Python中，in关键字的效率是多少，例如：

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

Answer 1

它取决于右手操作数：

操作员in并not in测试集合成员身份。[…]收集成员资格测试传统上已绑定到序列；如果该对象是一个序列，并且包含与该对象相等的元素，则该对象是该集合的成员。但是，对于许多其他对象类型来说，无需顺序即可支持成员资格测试是有意义的。特别是，字典（用于键）和集合支持成员资格测试。

类可以实现特殊方法__contains__来覆盖默认行为（遍历序列），因此与比较容器的每个元素相比，可以提供一种（或更少）有效的方式来测试成员资格。

成员资格测试运算符（in和not in）通常实现为序列的迭代。但是，容器对象可以为以下特殊方法提供更有效的实现，这也不要求对象是序列。

---

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