Python常用操作的复杂度
我们前面讲过list、deque、堆、字典树等高性能计算的技巧，这一节我们来整理一下Python中常用操作的时间复杂度。本文中的N表示容器的元素数量，K表示参数中元素的数量或参数的值。
- list
lst = list(range(10,20))
l1 = list(range(100,105))
操作 | 时间复杂度 | 描述 |
|---|---|---|
lst[2] | O(1) | 访问元素 |
lst.pop() | O(1) | 弹出最后一个值 |
lst.append(l1) | O(1) | 在末尾添加元素 |
lst.extend(l1) | O(K) | 在末尾逐个添加元素 |
lst.clear() | O(1) | 清空list |
lst.copy() | O(N) | 列表拷贝 |
lst.count(15) | O(N) | 元素计数 |
lst.remove(15) | O(N) | 删除一个元素 |
lst.reverse() | O(N) | 反序 |
lst.sort() | O(N*log(N)) | 排序 |
lst.insert(1,200) | O(N) | 在某一位置插入元素 |
del lst[0] | O(N) | 删除某个位置的元素 |
lst.index(15) | O(N) | 查找元素，并返回元素位置 |
bisect.bisect_left(lst, 15) | O(log(N)) | 有序列表使用bisect查找元素 |
- tuple
tuple因为不可写，因此操作相对较少
tpl = tuple(range(10))
操作 | 时间复杂度 | 描述 |
|---|---|---|
tpl[2] | O(1) | 访问元素 |
tpl.count(2) | O(N) | 元素计数 |
tpl.index(2) | O(N) | 查找元素，并返回元素位置 |
- set
ss1 = set(range(10))
ss2 = set(range(5,15))
操作 | 时间复杂度 | 描述 |
|---|---|---|
5 in ss1 | O(N) | 判断元素是否在set中 |
ss1 | ss2 | O(len(ss1)+len(ss2)) | 取并集，等同于ss1.union(ss2) |
ss1 & ss2 | O(len(s)*len(t)) | 取交集，等同于ss1.intersection(ss2) |
ss1 - ss2 | O(len(ss1)) | 取差集，等同于ss1.difference(ss2) |
ss1 ^ ss2 | O(len(ss1)*len(ss2)) | 取异或集，等同于 |
ss1.add(11) | O(1) | 增加元素 |
ss1.pop() | O(1) | 弹出一个元素 |
ss1.remove(5) | O(1) | 删除指定元素 |
- dict
dd = {'a':10,'b':20,'c':30,'d':40}
操作 | 时间复杂度 | 描述 |
|---|---|---|
dd['e'] = 50 | O(1) | 插入元素 |
dd['a'] | O(1) | 访问元素，等同于dd.get('a') |
del dd['a'] | O(1) | 删除元素 |
dd['b'] = 100 | O(1) | 修改元素 |
dd.pop('b') | O(1) | 弹出一个元素 |
dd.clear() | O(1) | 清空字典 |
- deque
双端队列需要我们手动导入后才能使用，也是Python中一种常用的类型
from collections import deque
deq = deque(range(10))
ll = list(range(10))
操作 | 时间复杂度 | 描述 |
|---|---|---|
deq.pop() | O(1) | 弹出最右侧的元素 |
deq.popleft() | O(1) | 弹出最左侧的元素 |
deq.append(1) | O(1) | 在右侧增加一个元素 |
deq.appendleft(1) | O(1) | 在左侧增加一个元素 |
deq.extend(ll) | O(K) | 在右侧逐个添加元素 |
deq.extendleft(ll) | O(K) | 在左侧逐个添加元素 |
deq.rotate(K) | O(K) | 旋转 |
deq.remove(5) | O(N) | 删除指定元素 |
deq[0] | O(1) | 访问第一个元素 |
deq[N-1] | O(1) | 访问最后一个元素 |
deq[N/2] | O(N) | 访问中间元素 |
Python高性能系列文章
欢迎关注微信公众号：Quant_Times