Python 中 *in* 运算符的复杂性

问题描述：

Python 中运算符的复杂度是多少in？是 theta(n) 吗？

和下面的一样吗？

def find(L, x):
   for e in L:
       if e == x:
           return True
   return False

L是一个列表。

解决方案 1：

的复杂性in完全取决于将会L变成。e in L`L.__contains__(e)`

有关几种内置类型的复杂性，请参阅此时间复杂度文档。

以下是摘要in：

• 列表 - 平均值：O（n）

• 集合/字典 - 平均：O（1），最差：O（n）

集合和字典的最坏情况 O(n) 非常罕见，但如果__hash__实现不当，则可能会发生这种情况。只有当集合中的所有内容都具有相同的哈希值时，才会发生这种情况。

解决方案 2：

这完全取决于容器的类型。散列容器（dict，set）使用散列，本质上是 O(1)。典型的序列（list，tuple）按您猜测的那样实现，是 O(n)。树的平均时间为 O(log n)。等等。这些类型中的每一种都有一种具有__contains__其大 O 特性的适当方法。

解决方案 3：

这取决于你测试的容器。通常情况下，它符合你的预期 - 对于有序数据结构，它是线性的；对于无序数据结构，它是常数。当然，两种类型（有序或无序）都可能由某种树的变体支持。