电话面试被问到了几个python常见操作的时间复杂度问题,这几年一直关注在业务逻辑的实现上这类基础反而记得不太清楚了,这里有必要重新复习一下,完整版:

TimeComplexity

列表

列表内部是由数组实现的,常见操作的时间复杂度如下:

操作平均情况最坏情况
Get查找O(1)O(1)
Set修改O(1)O(1)
Append追加O(1)O(1)
Len求长度O(1)O(1)
POP弹出O(1)O(1)
Insert插入O(n)O(n)
Del删除O(n)O(n)
Copy复制O(n)O(n)
Iteration迭代O(n)O(n)
IN查询O(n)O(n)
Min、MaxO(n)O(n)
Extend扩展O(k)O(k)
Sort排序O(nlogn)O(nlogn)

双端队列

内部是由双向列表实现的,所以对于2端的操作效率高,而对中间数据操作的效率底。

操作平均情况最坏情况
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)

字典

操作平均情况最坏情况
Get查找O(1)O(n)
Set修改O(1)O(n)
Del删除O(1)O(n)
IN查询O(1)O(n)
Iteration迭代O(n)O(n)
Copy复制O(n)O(n)

集合

内部实现和字典很像

操作平均情况最坏情况
IN查询O(1)O(n)
s&t交集O(min(len(s), len(t))O(len(s) * len(t))
st 并集O(len(s)+len(t))
s-t差集O(len(s))