python - 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

有a very detailed table on python wiki这回答了你的问题。

但是，在您的特定示例中，您应该使用 enumerate 来获取循环内可迭代的索引。像这样:

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