Python-list 和 dict 内置操作的时间复杂度
2018-09-17 本文已影响0人
言淦
Python的 list 数据结构
| 操作 | 操作说明 | 时间复杂度 |
|---|---|---|
| index(value) | 查找list某个元素的索引 | O(1) |
| a = index(value) | 索引赋值 | O(1) |
| append(value) | 队尾添加 | O(1) |
| pop() | 队尾删除 | O(1) |
| pop(index) | 根据索引删除某个元素 | O(n) |
| insert(index, value) | 根据索引插入某个元素 | O(n) |
| iterration | 列表迭代 | O(n) |
| search(in) | 列表搜索（其实就是in关键字） | O(n) |
| slice [x:y] | 切片, 获取x, y为O(1), 获取x,y 中间的值为O(k) | O(k) |
| del slice [x:y] | 删除切片，删除切片后数据需要重新移动/合并 | O(n) |
| reverse | 列表反转 | O(n) |
| sort | 排序 | O(nlogn) |
Python dict 数据结构
| 操作 | 操作说明 | 时间复杂度 |
|---|---|---|
| copy | 复制 | O(n) |
| get(value) | 获取 | O(1) |
| set(value) | 修改 | O(1) |
| delete(value) | 删除 | O(1) |
| search(in) | 字典搜索 | O(1) |
| iterration | 字典迭代 | O(n) |
