python列表函数的运行时复杂度是多少？ [英] What is the runtime complexity of python list functions?

问题描述

我正在写一个看起来像这样的python函数

I was writing a python function that looked something like this

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），但是很惊讶地发现，对于大型列表，这比我预期的要慢得多。

I had assumed that index access of lists was O(1), but was surprised to find that for large lists this was significantly slower than I expected.

我的问题是python列表是如何实现的，以下代码的运行时复杂度是什么？

My question, then, is how are python lists are implemented, and what is the runtime complexity of the following

• 索引： list [x]


• 从结尾开始： list.pop（）


• 从开头开始： list.pop（0）


• 扩展列表： list.append （x）

• Indexing: list[x]
• Popping from the end: list.pop()
• Popping from the beginning: list.pop(0)
• Extending the list: list.append(x)

需要额外的信用，拼接或任意弹出。

For extra credit, splicing or arbitrary pops.

推荐答案

有有关python Wiki的非常详细的表格，可以回答您的问题。

there is a very detailed table on python wiki which answers your question.

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

However, in your particular example you should use enumerate to get an index of an iterable within a loop. like so:

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

这篇关于python列表函数的运行时复杂度是多少？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！