Python 容器的时间复杂度

小嗷犬2023-03-242023-08-25

列表 List

列表是 Python 中常用的容器之一，它的时间复杂度如下：

操作	平均时间复杂度	最坏时间复杂度
Copy	O(n)	O(n)
Append	O(1)	O(1)
Pop last	O(1)	O(1)
Pop intermediate	O(n)	O(n)
Insert	O(n)	O(n)
Get item	O(1)	O(1)
Set item	O(1)	O(1)
Delete item	O(n)	O(n)
Iterate	O(n)	O(n)
Get slice	O(k)	O(k)
Del slice	O(n)	O(n)
Set slice	O(n+k)	O(n+k)
Extend	O(k)	O(k)
Sort	O(n log n)	O(n log n)
Multiply	O(nk)	O(nk)
x in s	O(n)
min(s),max(s)	O(n)
Get length	O(1)	O(1)

Python 中的列表是动态数组，它的底层是一个数组，当列表的长度超过数组的长度时，会重新分配一个更大的数组，然后将原数组中的元素复制到新数组中，这个过程的时间复杂度是 $O(n)$ 。除此之外，在列表的开头插入和删除元素的时间复杂度都是 $O(n)$ ，如果需要频繁地在列表的开头插入和删除元素，可以使用双端队列 collections.deque。

双端队列 collections.deque

双端队列是 Python 中的标准库 collections 中的一个容器，它的时间复杂度如下：

操作	平均时间复杂度	最坏时间复杂度
Copy	O(n)	O(n)
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)
rotate	O(k)	O(k)
remove	O(n)	O(n)
Get Length	O(1)	O(1)

双端队列的底层是一个双向链表，它在头尾两端的操作都比较块，但对中间的操作仍然较慢，在需要频繁地在列表的开头插入和删除元素时，可以使用双端队列 collections.deque。

集合 set

集合是 Python 中常用的容器之一，使用 hash 实现，元素查找效率极高，它的时间复杂度如下：

操作	平均时间复杂度	最坏时间复杂度	说明
x in s	O(1)	O(1)
Union s\|t	O(len(s) + len(t))
Intersection s&t	O(min(len(s), len(t)))	O(len(s) * len(t))	replace “min” with “max” if t is not a set
Multiple intersection s1&s2&…&sn		(n-1)*O(l) where l is max(len(s1),…,len(sn))
Difference s-t	O(len(s))
s.difference_update(t)	O(len(t))
Symmetric Difference s^t	O(len(s))	O(len(s) * len(t))
s.symmetric_difference_update(t)	O(len(t))	O(len(t) * len(s))

从表中我们可以看出 difference s-t 或 s.difference(t) 与就地差分 s.difference_update(t) 的时间复杂度是不同的，前者的时间复杂度是 $O(len(s))$ ，对于 s 中的每个元素，如果它不在 t 中，则将其添加到新集合中；后者的时间复杂度是 $O(len(t))$ ，对于 t 中的每个元素，请将其从 s 中删除。