Python常见操作时间复杂度
电话面试被问到了几个python常见操作的时间复杂度问题，这几年一直关注在业务逻辑的实现上这类基础反而记得不太清楚了，这里有必要重新复习一下，完整版：
列表
列表内部是由数组实现的，常见操作的时间复杂度如下：
| 操作 | 平均情况 | 最坏情况 |
|---|---|---|
| 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)) |
