问题描述
我正在写一个看起来像这样的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.
推荐答案
有,可以回答您的问题。
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列表函数的运行时复杂度是多少?的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持!