Python中列表函数的成本 [英] Cost of list functions in Python

问题描述

基于此旧线程，看起来Python中的列表函数是:

Based on this older thread, it looks like the cost of list functions in Python is:

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

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

Can anyone confirm whether this is still true in Python 2.6/3.x?

推荐答案

看看

Take a look here. It's a PEP for a different kind of list. The version specified is 2.6/3.0.

追加(向后插入)为O(1)，而插入(其他位置)为O(n).因此，是，看来这仍然是正确的.

Append (insertion to back) is O(1), while insertion (everywhere else) is O(n). So yes, it looks like this is still true.

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)

这篇关于Python中列表函数的成本的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！