我正在编写一个看起来像这样的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)
为了额外的信用,拼接或任意弹出。