什么是Python列表函数的运行时复杂性？
我正在写一个看起来像这样的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] - 从最后popup：
list.pop() - 从头开始：
list.pop(0) - 扩展列表：
list.append(x)
额外的信用，拼接或任意popup。
有一个非常详细的表格在Python的维基回答你的问题。
然而，在你的特定的例子中，你应该使用enumerate来获得循环内的迭代的索引。 像这样：
for i, item in enumerate(some_seq): bar(item, i)
答案是“未定义的”。 Python语言没有定义底层实现。 这里有一些你可能感兴趣的邮件列表的链接。
-
在Python的C实现中，Python的列表已经被实现为连续的向量。
-
我并不是说这些东西的O（）行为应该被保密或是什么。 但是，您需要在Python如何工作的背景下解释它们。
另外，编写循环的Pythonic方法会是这样的：
def foo(some_list): for item in some_list: bar(item)
列表确实是O（1）索引 – 它们被实现为一个具有比例分配的向量，所以执行得如您所愿。 你find这个代码的速度比你预期的要慢的原因是调用了“ range(0, len(some_list)) ”。
range()会创build一个新的指定大小的列表，所以如果some_list有1,000,000个项目，你会在前面创build一个新的百万个项目列表。 这种行为在python3（范围是一个迭代器），python2等价物是xrange ，甚至更好的情况下更改为你的情况， 枚举
还不能评论，所以
如果你需要索引和值，然后使用枚举：
for idx, item in enumerate(range(10, 100, 10)): print idx, item
Python列表实际上只是数组。 从而，
索引需要O（1）
对于stream行和再次追加它应该是O（1）根据文档
查看下面的链接了解详细信息：
http://dustycodes.wordpress.com/2012/03/31/pythons-data-structures-complexity-analysis/
