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 列表，以及以下的运行时复杂性是多少

为了额外的信用，拼接或任意弹出。

score 37 · Accepted Answer

python wiki上有一个非常详细的表格可以回答您的问题。

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

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

score 8 · Accepted Answer

答案是“未定义”。Python 语言没有定义底层实现。以下是您可能感兴趣的邮件列表主题的一些链接。

此外，编写循环的更 Pythonic 方式是：

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

score 6 · Accepted Answer

列表确实是 O(1) 索引 - 它们被实现为具有比例过度分配的向量，因此执行得如您所愿。您发现此代码比您预期慢的可能原因是对“ range(0, len(some_list))”的调用。

range()创建一个指定大小的新列表，因此如果 some_list 有 1,000,000 个项目，您将在前面创建一个新的百万项目列表。这种行为在 python3 中发生了变化（范围是一个迭代器），python2 的等效项是xrange，或者更适合您的情况，枚举

score 3 · Accepted Answer

如果您需要索引和值，请使用枚举：

for idx, item in enumerate(range(10, 100, 10)):
    print idx, item

score 1 · Accepted Answer

Python list 实际上只是数组。因此，

索引需要 O(1)

根据文档，对于 pop 并再次追加，它应该是 O(1)

查看以下链接了解详情：

5 回答 5