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

Question

inPython中运算符的复杂性是多少？是θ（n）吗？

和下面的一样吗？

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

L是一个列表。

Answer 1

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

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

以下是以下内容的摘要in：

• 列表 - 平均：O(n)
• set/dict - 平均：O(1)，最差：O(n)

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

Answer 2

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

Answer 3

这取决于您正在测试的容器。这通常是您所期望的——有序数据结构是线性的，无序数据结构是常数。当然，有两种类型（有序或无序）可能由树的某些变体支持。