Python中list.index（x）的复杂性

Question

我指的是这个：http://docs.python.org/tutorial/datastructures.html

就big O符号而言，list.index(x)函数的运行时间是多少？

Answer 1

对于线性搜索（例如list.index），任何列表实现都将具有O（n）复杂性。尽管可能有一些古怪的实现在那里做得更糟。。。

通过使用不同的数据结构（如有序列表或集合），可以提高查找的复杂性。这些通常用二叉树实现。然而，这些数据结构对它们所包含的元素施加了约束。在二叉树的情况下，元素需要是可排序的，但是查找成本降到O（log n）。

如前所述，请查看标准Python数据结构的运行时成本： http://wiki.python.org/moin/TimeComplexity

Answer 2

根据上述文件：

list.index(x)

Return the index in the list of the first item whose value is x. It is an error if there is no such item.

这意味着搜索。你实际上在做x in s，但不是返回True或False，而是返回x的索引。因此，我将使用O（n）的listed time complexity。

Answer 3

是O（n），也可以查看：http://wiki.python.org/moin/TimeComplexity

This page documents the time-complexity (aka "Big O" or "Big Oh") of various operations in current CPython. Other Python implementations (or older or still-under development versions of CPython) may have slightly different performance characteristics. However, it is generally safe to assume that they are not slower by more than a factor of O(log n)...