python - 在某个位置插入列表的成本/复杂性是多少？

Question

在 Python 中，一个 list有 list.insert(i, x) 到“在给定位置插入一个项目。”。在 C++ 中，有一个 list以及。在 C++ 中，在任何地方插入元素的成本/复杂性是 O(1)。 Python 列表是否相同？如果没有，是否可以使用其他方法在 Python 中获得 O(1) 插入时间？

Answer 1

列表

Average Case 假定参数是随机均匀生成的。

在内部，列表表示为数组；最大的成本来自超出当前分配大小的增长(因为所有东西都必须移动)，或者来自插入或删除接近开始的地方(因为之后的所有东西都必须移动)。如果您需要在两端添加/删除，请考虑改用 collections.deque。

所以在给定位置插入一个元素总是有O(n)的时间复杂度，因为insert方法和slicing都有时间O(n) 和 O(k) 的复杂度。 只有在列表末尾插入的append 具有O(1) 时间复杂度。 来自 Python Wiki

Lists:
                               Complexity
Operation     | Example      | Class         | Notes
--------------+--------------+---------------+-------------------------------
Index         | l[i]         | O(1)          |
Store         | l[i] = 0     | O(1)          |
Length        | len(l)       | O(1)          |
Append        | l.append(5)  | O(1)          |
Clear         | l.clear()    | O(1)          | similar to l = []

Slice         | l[a:b]       | O(b-a)        | l[1:5]:O(l)/l[:]:O(len(l)-0)=O(N)
Extend        | l.extend(...)| O(len(...))   | depends only on len of extension
Construction  | list(...)    | len(...)      | depends on lenghth of argument

check ==, !=  | l1 == l2     | O(N)          |
Insert        | l[a:b] = ... | O(N)          |
Delete        | del l[i]     | O(N)          | 
Remove        | l.remove(...)| O(N)          | 
Containment   | x in/not in l| O(N)          | searches list
Copy          | l.copy()     | O(N)          | Same as l[:] which is O(N)
Pop           | l.pop(...)   | O(N)          |
Pop           | l.pop()      | O(1)          | same as l.pop(-1), popping at end
Extreme value | min(l)/max(l)| O(N)          |
Reverse       | l.reverse()  | O(N)          |
Iteration     | for v in l:  | O(N)          |

Sort          | l.sort()     | O(N Log N)    | key/reverse doesn't change this
Multiply      | k*l          | O(k N)        | 5*l is O(N): len(l)*l is O(N**2)

来自 here