Python中in运算符的复杂性

Question

Python中in运算符的复杂性是什么？是θ(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)最坏情况非常罕见,但如果__hash__实施不当则可能发生.仅当集合中的所有内容具有相同的哈希值时,才会发生这种情况

Answer 2

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

@Woot4Moo：当您谈论渐近复杂性时，这无关紧要。生成散列的开销是恒定的。当您处理 N 的小值时，分析变得很重要，因为对于小 N，例如 100 >> 2N。但这是与 OP 所询问的不同的问题；对于巨大的 N，100 << 2N，这就是复杂性的意义所在。 (2认同)

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