列表list
- 以完全随机的列表考虑平均情况。
列表是以数组(Array)实现的。最大的开销发生在超过当前分配大小的增长,这种情况下所有元素都需要移动;或者是在起始位置附近插入或者删除元素,这种情况下所有在该位置后面的元素都需要移动。如果你需要在一个队列的两端进行增删的操作,应当使用collections.deque(双向队列)
操作 | 平均情况 | 最坏情况 |
---|---|---|
复制 | O(n) | O(n) |
append | O(1) | O(1) |
插入 | O(n) | O(n) |
取元素 | O(1) | O(1) |
更改元素 | O(1) | O(1) |
删除元素 | O(n) | O(n) |
遍历 | O(n) | O(n) |
取切片 | O(k) | O(k) |
删除切片 | O(n) | O(n) |
更改切片 | O(k+n) | O(k+n) |
extend | O(k) | O(k) |
排序 | O(n logn) | O(n logn) |
列表乘法 | O(nk) | O(nk) |
x in s | O(n) | |
min(s), max(s) | O(n) | |
计算长度 | O(1) | O(1) |
双端队列queue
deque (double-ended queue,双向队列)是以双向链表的形式实现的 (Well, a list of arrays rather than objects, for greater efficiency)。双向队列的两端都是可达的,但从查找队列中间的元素较为缓慢,增删元素就更慢了。
操作 | 平均情况 | 最坏情况 |
---|---|---|
复制 | O(n) | O(n) |
append | O(1) | O(1) |
appendleft | O(1) | O(1) |
pop | O(1) | O(1) |
popleft | O(1) | O(1) |
extend | O(k) | O(k) |
extendleft | O(k) | O(k) |
rotate | O(k) | O(k) |
remove | O(n) | O(n) |
集合set
操作 | 平均情况 | 最坏情况 | |
---|---|---|---|
x in s | O(1) | O(n) | |
并集 s\ | t | O(len(s)+len(t)) | |
交集 s&t | O(min(len(s), len(t)) | O(len(s) * len(t)) | |
差集 s-t | O(len(s)) | ||
s.difference_update(t) | O(len(t)) | ||
对称差集 s^t | O(len(s)) | O(len(s) * len(t)) | |
s.symmetric_difference_update(t) | O(len(t)) | O(len(t) * len(s)) |
字典dict
下列字典的平均情况基于以下假设:
- 对象的散列函数足够鲁棒性(robust),不会发生冲突。
- 字典的键是从所有可能的键的集合中随机选择的。
小窍门:只使用字符串作为字典的键。这么做虽然不会影响算法的时间复杂度,但会对常数项产生显著的影响,这决定了你的一段程序能多快跑完。
操作 | 平均情况 | 最坏情况 |
---|---|---|
复制 | O(n) | O(n) |
取元素 | O(1) | O(n) |
更改元素 | O(1) | O(n) |
删除元素 | O(1) | O(n) |
遍历 | O(n) | O(n) |