Python列表函数的时间复杂度是什么？

Question

我在写一个Python函数，代码大概是这样的：

def foo(some_list):
   for i in range(0, len(some_list)):
       bar(some_list[i], i)

然后我用这种方式来调用它：

x = [0, 1, 2, 3, ... ]
foo(x)

我原本以为访问列表中的元素是很快的，时间复杂度是O(1)，但是我发现对于很大的列表，这个速度比我想象的要慢很多。

所以我想问，Python中的列表是怎么实现的？以下操作的运行时间复杂度分别是多少呢：

• 索引访问：list[x]
• 从末尾弹出元素：list.pop()
• 从开头弹出元素：list.pop(0)
• 扩展列表：list.append(x)

如果能多说一下切片或者任意位置弹出的情况就更好了。

Answer 1

列表的索引确实是 O(1)，也就是说查找某个元素的速度是很快的。它们是通过一种叫做向量的方式实现的，并且会预留一些额外的空间，所以表现得和你预期的一样。你觉得代码运行得比预期慢，很可能是因为调用了 "range(0, len(some_list))"。

range() 会创建一个指定大小的新列表，所以如果你的 some_list 有 1,000,000 个项目，调用这个函数时就会提前创建一个包含一百万个元素的新列表。在 Python 3 中，这种行为发生了变化，range 变成了一个迭代器。在 Python 2 中，类似的功能是 xrange，而对于你的情况，更好的选择是 enumerate。

Answer 2

答案是“未定义”。Python 语言并没有明确规定其底层实现。这里有一些你可能会感兴趣的邮件列表讨论链接。

• 确实，Python 的列表在 C 语言实现的 Python 中一直是作为连续的向量来实现的。

• 我并不是说这些东西的 O() 行为应该被保密。但你需要在理解 Python 一般工作原理的背景下来解读它们。

另外，更符合 Python 风格的写法应该是这样的：

def foo(some_list):
   for item in some_list:
       bar(item)

Answer 3

在Python的维基百科上，有一张非常详细的表格，可以解答你的问题，地址是这里。

不过，在你提到的这个例子中，你应该使用 enumerate 来在循环中获取可迭代对象的索引。可以这样写：

for i, item in enumerate(some_seq):
    bar(item, i)