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

Question

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

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

score 55 · Accepted Answer

列表的复杂性是：

O(n)

对于集合，它是：

O(1)

score 42 · Accepted Answer

这取决于右手操作数：

运算符in和not in集合成员的测试。[...] 集合成员资格测试传统上与序列绑定；如果集合是一个序列并且包含与该对象相等的元素，则该对象是该集合的成员。但是，对于许多其他对象类型来说，支持成员资格测试而不是序列是有意义的。特别是，字典（用于键）和集合支持成员资格测试。

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

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

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

2 回答 2