我们前面讲过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 dequedeq = 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
本文分享自微信公众号 - 科学计算Tech（Quant_Times）。
如有侵权，请联系 support@oschina.cn 删除。
本文参与“OSC源创计划”，欢迎正在阅读的你也加入，一起分享。
