Python中列表函数的成本

Question

基于这个旧线程,看起来Python中列表函数的成本是:

• 随机访问:O(1)
• 插入/删除到前面:O(n)
• 插入/删除:O(1)

任何人都可以确认在Python 2.6/3.x中是否仍然如此？

Answer 1

看看这里.这是一个针对不同类型列表的PEP.指定的版本是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)

Answer 2

Python 3主要是一个渐进式的变化,数据结构及其复杂性没有大的变化.

Python集合的规范来源是Wiki上的TimeComplexity.