Python 列表、队列、集合、字典各方法的时间复杂度(list、deque、set、dict)

本文中,’n’ 代表容器中元素的数量,’k’ 代表元素值,或者参数的数量,‘i’ 表示索引值。

列表(list)

操作 时间复杂度
复制 O(n)
append O(1)
insert O(n)
extend O(k)
索引 O(1)
赋值(修改值) O(1)
pop() O(1)
pop(i) O(n)
remove(k) O(n)
遍历 O(n)
切片 O(k)
排序 O(n log n)
in O(n)
max()、min() O(n)
len() O(1)

双向队列(collections.deque)

操作 时间复杂度
复制 O(n)
append O(1)
appendleft O(1)
extend O(k)
extendleft O(k)
pop O(1)
popleft O(1)
rotate O(k)
remove O(n)

集合(set)

操作 时间复杂度
in O(n)
add O(1)
pop() O(1)
pop(i) O(n)
remove(k) O(n)
遍历 O(n)
并集 (s,t) O(len(s)+len(t))
交集 s&t O(len(s) * len(t))
差集 s-t O(len(s))
s.difference_update(t) O(len(t))
对称差集 s^t O(len(s) * len(t))
s.symmetric_difference_update(t) O(len(t) * len(s))

字典(dict)

操作 时间复杂度
复制 O(n)
遍历 O(n)
索引 O(1)
删除 O(1)
更改元素 O(1)
in O(1)

你可能感兴趣的