Python常见操作时间复杂度

电话面试被问到了几个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、Max O(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))
我来评几句
登录后评论

已发表评论数()

相关站点

+订阅
热门文章