Python中列表函数的开销

Question

根据这个较早的讨论，在Python中，列表操作的成本大致是：

• 随机访问：O(1)（也就是说，查找某个元素的时间是固定的，不会随着列表的大小变化）
• 在前面插入/删除：O(n)（这意味着如果你在列表的前面添加或删除元素，所需的时间会随着列表的长度增加而增加）
• 在后面插入/删除：O(1)（这表示在列表的末尾添加或删除元素所需的时间是固定的，不受列表长度影响）

有人能确认这些在Python 2.6/3.x中是否仍然适用吗？

Answer 1

没错，把东西插到前面会导致所有的元素都得移动一下，腾出位置来。

collections.deque 提供了类似的功能，但它在两边插入时更高效。

Answer 2

Python 3 主要是一个渐进式的改进，没有对数据结构和它们的复杂性做出大的改变。

关于 Python 集合的权威资料可以在维基百科的 时间复杂度 页面找到。

Answer 3

你可以看看这里。这是一个关于另一种列表的PEP（Python增强提案）。提到的版本是2.6/3.0。

在这个列表中，添加元素到最后面（也叫做追加）是O(1)，而在其他地方插入元素的时间复杂度是O(n)。所以没错，看起来这个说法还是成立的。

Operation...Complexity
Copy........O(n) 
Append......O(1)
Insert......O(n) 
Get Item....O(1)
Set Item....O(1)
Del Item....O(n) 
Iteration...O(n)
Get Slice...O(k)
Del Slice...O(n)
Set Slice...O(n+k)
Extend......O(k) 
Sort........O(n log n)
Multiply....O(nk)