Python内置类型操作的时间复杂度

原文链接：https://docs.python.org/3.16/library/time-complexity.html

本文档记录了 CPython 中各类内置类型操作的时间复杂度。其他 Python 实现可能具有不同的性能特征。此外，所列出的开销均假设为精确的内置类型，因为子类的实例可能具有不同的开销。

我们使用大 O 符号来描述操作的运行时间如何随其输入规模增长。除非另有说明，n 表示容器中当前元素的数量，k 是一个数值参数的值，例如索引或重复次数。

list ¶

列表是可变序列；有关实现的更多细节，请参阅 CPython 中的列表是如何实现的。最大的开销来自超出当前分配大小（因为所有元素都必须移动），或在靠近开头处插入或删除（因为之后的所有元素都必须移动）。如果你需要在两端添加或删除元素，请考虑改用 collections.deque。

操作	复杂度
复制（l.copy()）	O(n)
追加（l.append(x)）[1]	O(1)
弹出（l.pop(k)）[1] [2]	O(n − k)
插入（l.insert(k, x)）[1] [2]	O(n − k)
获取元素（l[k]）	O(1)
设置元素（l[k] = x）	O(1)
删除元素（del l[k]）[2]	O(n − k)
迭代	O(n)
获取切片（l[i:j]）	O(j − i)
设置切片（l[i:j] = t）[1]	若 len(t) == j − i 则为 O(j − i)，否则为 O(n − i + len(t))
删除切片（del l[i:j]）	O(n − i)
扩展（l.extend(t)）[1] [3]	O(len(t))
排序（l.sort()）[4]	O(n log n)
拼接（l1 + l2）	O(len(l1) + len(l2))
乘法（l * k）	O(nk)
x in l	O(n)
min(l), max(l)	O(n)
获取长度（len(l)）[5]	O(1)

tuple ¶

元组是不可变序列。由于元组永远不会改变，因此不存在插入或删除的开销，且复制一个元组只需返回同一个对象，所以是常数时间（O(1)）。

操作	复杂度
复制（tuple(t)）	O(1)
获取元素（t[k]）	O(1)
获取切片（t[i:j]）	O(j − i)
拼接（t1 + t2）	O(len(t1) + len(t2))
乘法（t * k）	O(nk)
迭代	O(n)
x in t	O(n)
min(t), max(t)	O(n)
获取长度（len(t)）[5]	O(1)

dict, frozendict ¶

字典对象所列出的时间均为平均情况下的时间，因为它们假设对象的哈希函数足够健壮，使得冲突不常见。它们还假设键在所有可能的键集合中分布良好。在最坏情况下，当每个键都哈希到同一个值时，下面每个 O(1) 操作都将花费 O(n) 时间。它们还假设对键进行哈希和比较的开销是 O(1)。有关实现的更多细节，请参阅 CPython 中的字典是如何实现的。

frozendict 是不可变的，因此不支持设置、删除或更新元素。下面的其他操作同样适用于它，且开销相同。

操作	复杂度
key in d	O(1)
复制（d.copy()）[6] [7]	O(n)
获取元素（d[key], d.get(key)）	O(1)
设置元素（d[key] = value）[1]	O(1)
删除元素（del d[key], d.pop(key)）	O(1)
更新（d.update(t), d |= t）[1] [3] [7]	O(len(t))
迭代 [7]	O(n)
获取长度（len(d)）[5]	O(1)

set, frozenset ¶

请参阅 dict，因为 set 和 frozenset 的实现与之类似，且适用相同的注意事项。在最坏情况下，O(1) 操作将花费 O(n) 时间，而查找每个元素的操作也会相应退化。

frozenset 是不可变的，因此不支持添加、丢弃或原地更新操作。下面的其他操作同样适用于它，且开销相同。

操作	复杂度
x in s	O(1)
复制（s.copy()）[6] [7]	O(n)
添加（s.add(x)）[1]	O(1)
丢弃（s.discard(x), s.remove(x)）	O(1)
并集（s1 | s2, s1.union(s2)）[7]	O(len(s1) + len(s2))
更新（s1 |= s2, s1.update(s2)）[1] [7]	O(len(s2))
交集（s1 & s2, s1.intersection(s2)）[7] [8]	O(min(len(s1), len(s2)))
交集更新（s1 &= s2, s1.intersection_update(s2)）[1] [7] [8]	O(min(len(s1), len(s2)))
差集（s1 - s2, s1.difference(s2)）[7] [9]	O(len(s1))
差集更新（s1 -= s2, s1.difference_update(s2)）[1] [7] [8]	O(min(len(s1), len(s2)))
对称差集（s1 ^ s2, s1.symmetric_difference(s2)）[7]	O(len(s1) + len(s2))
对称差集更新（s1 ^= s2, s1.symmetric_difference_update(s2)）[1] [7]	O(len(s2))
获取长度（len(s)）[5]	O(1)

str, bytes, bytearray ¶

str 和 bytes 对象分别是字符和字节的不可变序列。与元组一样，复制它们会返回原始对象。bytearray 是可变的，并且额外支持 list 的修改操作（除 sort() 外），开销相同。但是，使用 del 在开头删除（del b[0], del b[:k]）只会推进缓冲区的起始位置，而不是移动剩余的字节，其摊销复杂度为 O(1)。

操作	复杂度
获取元素（s[k]）	O(1)
获取切片（s[i:j]）	O(j − i)
拼接（s + t）[10]	O(len(s) + len(t))
乘法（s * k）	O(nk)
子串搜索（x in s, s.find(x), s.index(x)）[11]	O(n)
反向子串搜索（s.rfind(x), s.rindex(x)）[11] [12]	O(n × len(x))
编码或解码 [13]	O(n)
迭代	O(n)
获取长度（len(s)）[5]	O(1)

memoryview ¶

memoryview 对象允许 Python 代码在不复制的情况下访问支持缓冲区协议的对象的内部数据。特别是，对 memoryview 进行切片会返回指向同一缓冲区的新视图。

操作	复杂度
创建（memoryview(obj)）	O(1)
获取元素（v[k]）	O(1)
获取切片（v[i:j]）	O(1)
索引（v.index(x)）[11] [14]	O(n)
计数（v.count(x)）[14]	O(n)
转换为 bytes（v.tobytes(), bytes(v)）	O(n)
获取长度（len(v)）[5]	O(1)

range ¶

range 对象根据其 start、stop 和 step 值按需计算其元素，因此大多数操作不依赖于 range 的长度。

操作	复杂度
获取元素（r[k]）	O(1)
获取切片（r[i:j]）	O(1)
x in r [15]	O(1)
索引和计数（r.index(x), r.count(x)）[15]	O(1)
迭代	O(n)
min(r), max(r)	O(n)
获取长度（len(r)）[5]	O(1)

注释 ¶

---

脚注说明（保留原文编号对应关系）：

• [1] 这些操作可能会触发列表/字典/集合的内部重新分配，其摊销复杂度为 O(1)，但偶尔会出现 O(n) 的峰值。
• [2] pop() 不带参数时（即 l.pop()）为 O(1)，因为它从末尾弹出。
• [3] extend/update 的复杂度取决于可迭代对象 t 的长度。
• [4] list.sort() 使用 Timsort 算法，平均和最坏情况均为 O(n log n)。
• [5] len() 对所有内置容器都是 O(1)，因为长度被缓存在对象内部。
• [6] 对于 dict 和 set，copy() 在 CPython 3.5+ 中通过引用计数共享底层哈希表实现 O(1) 的浅拷贝，但最坏情况下仍为 O(n)。
• [7] 迭代字典/集合时，顺序取决于插入顺序（Python 3.7+ 保证）。
• [8] 交集操作通过遍历较小的集合并在较大的集合中查找实现。
• [9] 差集操作通过遍历第一个集合并检查成员关系实现。
• [10] 字符串/字节串拼接会创建新对象，多次拼接建议使用 str.join() 或 io.StringIO。
• [11] 子串搜索使用 Two-Way 算法，最坏情况 O(n × m)，但平均情况接近 O(n)。
• [12] 反向搜索需要特殊处理，复杂度与模式长度相关。
• [13] 编码/解码复杂度取决于具体编解码器，常见编解码器（如 UTF-8）为线性时间。
• [14] memoryview 的 index 和 count 逐元素比较。
• [15] range 的成员测试和索引通过算术计算实现，无需遍历。