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

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

和下面的一样吗？

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

L是一个列表。

119535 次浏览
小开

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

小开
最佳答案

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

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

以下是 in的摘要:

  • 列表-平均值: O (n)
  • Set/dict-平均值: O (1) ，最差值: O (n)

集合和字母表的 O (n)最坏情况是非常少见的，但是如果 __hash__实现得不好，就会发生这种情况。只有当集合中的所有内容都具有相同的散列值时才会发生这种情况。

小开

这取决于你要测试的容器。它通常是您所期望的——有序数据结构是线性的，无序数据结构是常量。当然，这两种类型(有序或无序)都可能由树的某种变体支持。


提交答案