Python中list.index(x)的复杂度
我指的是这个链接：http://docs.python.org/tutorial/datastructures.html
那么，list.index(x) 这个函数的运行时间在大O表示法中是怎样的呢？
6 个回答
5
任何列表的实现，在进行线性搜索（比如使用list.index）时，都会有O(n)的复杂度。虽然可能有一些奇怪的实现会更糟糕……
你可以通过使用不同的数据结构来提高查找的效率，比如有序列表或集合。这些通常是用二叉树来实现的。不过，这些数据结构对它们包含的元素有一些限制。以二叉树为例，里面的元素需要是可以排序的，但这样查找的成本就降低到了O(log n)。
之前提到过，可以查看标准Python数据结构的运行时间成本：http://wiki.python.org/moin/TimeComplexity
14
根据文档的说明：
list.index(x)返回列表中第一个值为 x 的项目的索引。如果没有这样的项目，这将是一个错误。
这意味着需要进行搜索。你实际上是在做 x in s 的操作，但不是返回 True 或 False，而是返回 x 的索引。因此，我认为它的时间复杂度是 O(n)，可以参考一下 列出的时间复杂度。
80
这是O(n)的复杂度，另外可以看看这个链接：http://wiki.python.org/moin/TimeComplexity
这个页面记录了当前CPython中各种操作的时间复杂度（也叫“Big O”或“Big Oh”）。其他的Python版本（或者旧版、正在开发中的CPython版本）可能在性能上会有些不同。不过，通常可以认为它们的速度不会比O(log n)慢太多……