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

# 内置类型操作的时间复杂度 来源：https://docs.python.org/3.16/library/time-complexity.html 本页面记录了 CPython 中内置类型各种操作的时间复杂度。其他 Python 实现可能具有不同的性能特性。此外，列出的成本假设的是精确的内置类型，因为子类的实例可能具有不同的成本。 我们使用大 O 表示法 (https://en.wikipedia.org/wiki/Big_O_notation) 来描述操作的运行时间如何随输入规模增长。除非另有说明，*n* 表示容器中当前的元素数量，*k* 是数字参数的值，例如索引或重复计数。 ## `list`¶ (https://docs.python.org/3.16/library/time-complexity.html#list) 列表是可变序列；有关实现的更多细节，请参见 CPython 中列表是如何实现的？ (https://docs.python.org/3.16/faq/design.html#how-are-lists-implemented)。最大的开销来自于超出当前分配大小进行增长（因为所有元素都必须移动），或者在靠近开头的位置插入或删除（因为之后的所有元素都必须移动）。如果需要在两端添加或删除元素，请考虑改用 `collections\.deque` (https://docs.python.org/3.16/library/collections.html#collections.deque)。 操作 复杂度 复制（`l\.copy\(\)`） *O*\(*n*\) 追加（`l\.append\(x\)`）[\[1\]](https://docs.python.org/3.16/library/time-complexity.html#id54) *O*\(1\) 弹出（`l\.pop\(k\)`）[\[1\]](https://docs.python.org/3.16/library/time-complexity.html#id54)[\[2\]](https://docs.python.org/3.16/library/time-complexity.html#id55) *O*\(*n*\-*k*\) 插入（`l\.insert\(k, x\)`）[\[1\]](https://docs.python.org/3.16/library/time-complexity.html#id54)[\[2\]](https://docs.python.org/3.16/library/time-complexity.html#id55) *O*\(*n*\-*k*\) 获取元素（`l\[k\]`） *O*\(1\) 设置元素（`l\[k\] = x`） *O*\(1\) 删除元素（`del l\[k\]`）[\[2\]](https://docs.python.org/3.16/library/time-complexity.html#id55) *O*\(*n*\-*k*\) 迭代 *O*\(*n*\) 获取切片（`l\[i:j\]`） *O*\(*j*\-*i*\) 设置切片（`l\[i:j\] = t`）[\[1\]](https://docs.python.org/3.16/library/time-complexity.html#id54) *O*\(*j*\-*i*\) 如果 len\(*t*\) ==*j*\-*i*，否则为*O*\(*n*\-*i*\+ len\(*t*\)\) 删除切片（`del l\[i:j\]`） *O*\(*n*\-*i*\) 扩展（`l\.extend\(t\)`）[\[1\]](https://docs.python.org/3.16/library/time-complexity.html#id54)[\[3\]](https://docs.python.org/3.16/library/time-complexity.html#id56) *O*\(len\(*t*\)\) 排序（`l\.sort\(\)`）[\[4\]](https://docs.python.org/3.16/library/time-complexity.html#id57) *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\]](https://docs.python.org/3.16/library/time-complexity.html#id58) *O*\(1\) ## `tuple`¶ (https://docs.python.org/3.16/library/time-complexity.html#tuple) `tuple` (https://docs.python.org/3.16/library/stdtypes.html#tuple) 是不可变 (https://docs.python.org/3.16/glossary.html#term-immutable) 序列。因为元组永远不能改变，所以没有插入或删除的开销，并且复制只是返回同一个对象，因此是常数时间 *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\]](https://docs.python.org/3.16/library/time-complexity.html#id58) *O*\(1\) ## `dict`，`frozendict`¶ (https://docs.python.org/3.16/library/time-complexity.html#dict-frozendict) 为 dict 对象列出的时间是平均情况下的时间，因为它们假设对象的哈希函数足够健壮，使得冲突不常见。它们还假设键在可能键的集合中分布良好。在最坏的情况下，当每个键都哈希到同一个值时，下面每个*O*\(1\)操作反而需要*O*\(*n*\)时间。它们还假设对键进行哈希和比较是*O*\(1\)。有关实现的更多细节，请参见 CPython 中字典是如何实现的？ (https://docs.python.org/3.16/faq/design.html#how-are-dictionaries-implemented)。 `frozendict` (https://docs.python.org/3.16/library/stdtypes.html#frozendict) 是不可变的，因此不支持设置、删除或更新元素。下面的其他操作对其适用，且成本相同。 操作 复杂度 `key in d` *O*\(1\) 复制（`d\.copy\(\)`）[\[6\]](https://docs.python.org/3.16/library/time-complexity.html#id59)[\[7\]](https://docs.python.org/3.16/library/time-complexity.html#id60) *O*\(*n*\) 获取元素（`d\[key\]`，`d\.get\(key\)`） *O*\(1\) 设置元素（`d\[key\] = value`）[\[1\]](https://docs.python.org/3.16/library/time-complexity.html#id54) *O*\(1\) 删除元素（`del d\[key\]`，`d\.pop\(key\)`） *O*\(1\) 更新（`d\.update\(t\)`，`d \|= t`）[\[1\]](https://docs.python.org/3.16/library/time-complexity.html#id54)[\[3\]](https://docs.python.org/3.16/library/time-complexity.html#id56)[\[7\]](https://docs.python.org/3.16/library/time-complexity.html#id60) *O*\(len\(*t*\)\) 迭代[\[7\]](https://docs.python.org/3.16/library/time-complexity.html#id60) *O*\(*n*\) 获取长度（`len\(d\)`）[\[5\]](https://docs.python.org/3.16/library/time-complexity.html#id58) *O*\(1\) ## `set`，`frozenset`¶ (https://docs.python.org/3.16/library/time-complexity.html#set-frozenset) 参考 `dict` (https://docs.python.org/3.16/library/stdtypes.html#dict)，因为 `set` (https://docs.python.org/3.16/library/stdtypes.html#set) 和 `frozenset` (https://docs.python.org/3.16/library/stdtypes.html#frozenset) 的实现类似，且同样的注意事项适用。在最坏的情况下，*O*\(1\)操作反而需要*O*\(*n*\)时间，而查找每个元素的操作会相应地退化。 `frozenset` (https://docs.python.org/3.16/library/stdtypes.html#frozenset) 是不可变的 (https://docs.python.org/3.16/glossary.html#term-immutable)，因此不支持添加、丢弃或就地更新操作。下面的其他操作对其适用，且成本相同。 操作 复杂度 `x in s` *O*\(1\) 复制（`s\.copy\(\)`）[\[6\]](https://docs.python.org/3.16/library/time-complexity.html#id59)[\[7\]](https://docs.python.org/3.16/library/time-complexity.html#id60) *O*\(*n*\) 添加（`s\.add\(x\)`）[\[1\]](https://docs.python.org/3.16/library/time-complexity.html#id54) *O*\(1\) 丢弃（`s\.discard\(x\)`，`s\.remove\(x\)`） *O*\(1\) 联合（`s1 \| s2`，`s1\.union\(s2\)`）[\[7\]](https://docs.python.org/3.16/library/time-complexity.html#id60) *O*\(len\(*s1*\) \+ len\(*s2*\)\) 更新（`s1 \|= s2`，`s1\.update\(s2\)`）[\[1\]](https://docs.python.org/3.16/library/time-complexity.html#id54)[\[7\]](https://docs.python.org/3.16/library/time-complexity.html#id60) *O*\(len\(*s2*\)\) 交集（`s1 & s2`，`s1\.intersection\(s2\)`）[\[7\]](https://docs.python.org/3.16/library/time-complexity.html#id60)[\[8\]](https://docs.python.org/3.16/library/time-complexity.html#id61) *O*\(min\(len\(*s1*\), len\(*s2*\)\)\) 交集更新（`s1 &= s2`，`s1\.intersection\_update\(s2\)`）[\[1\]](https://docs.python.org/3.16/library/time-complexity.html#id54)[\[7\]](https://docs.python.org/3.16/library/time-complexity.html#id60)[\[8\]](https://docs.python.org/3.16/library/time-complexity.html#id61) *O*\(min\(len\(*s1*\), len\(*s2*\)\)\) 差集（`s1 \- s2`，`s1\.difference\(s2\)`）[\[7\]](https://docs.python.org/3.16/library/time-complexity.html#id60)[\[9\]](https://docs.python.org/3.16/library/time-complexity.html#id62) *O*\(len\(*s1*\)\) 差集更新（`s1 \-= s2`，`s1\.difference\_update\(s2\)`）[\[1\]](https://docs.python.org/3.16/library/time-complexity.html#id54)[\[7\]](https://docs.python.org/3.16/library/time-complexity.html#id60)[\[8\]](https://docs.python.org/3.16/library/time-complexity.html#id61) *O*\(min\(len\(*s1*\), len\(*s2*\)\)\) 对称差集（`s1 ^ s2`，`s1\.symmetric\_difference\(s2\)`）[\[7\]](https://docs.python.org/3.16/library/time-complexity.html#id60) *O*\(len\(*s1*\) \+ len\(*s2*\)\) 对称差集更新（`s1 ^= s2`，`s1\.symmetric\_difference\_update\(s2\)`）[\[1\]](https://docs.python.org/3.16/library/time-complexity.html#id54)[\[7\]](https://docs.python.org/3.16/library/time-complexity.html#id60) *O*\(len\(*s2*\)\) 获取长度（`len\(s\)`）[\[5\]](https://docs.python.org/3.16/library/time-complexity.html#id58) *O*\(1\) ## `str`，`bytes`，`bytearray`¶ (https://docs.python.org/3.16/library/time-complexity.html#str-bytes-bytearray) `str` (https://docs.python.org/3.16/library/stdtypes.html#str) 和 `bytes` (https://docs.python.org/3.16/library/stdtypes.html#bytes) 对象分别是字符和字节的不可变序列。与元组一样，复制它们返回原始对象。`bytearray` (https://docs.python.org/3.16/library/stdtypes.html#bytearray) 是可变的，并且额外支持 `list` (https://docs.python.org/3.16/library/stdtypes.html#list) 的变更操作（`sort\(\)` 除外），成本相同。但是，使用 `del`（`del b\[0\]`，`del b\[:k\]`）在前端删除只会推进缓冲区的起始位置，而不是移动剩余字节，并且是摊销 *O*\(1\)。 操作 复杂度 获取元素（`s\[k\]`） *O*\(1\) 获取切片（`s\[i:j\]`） *O*\(*j*\-*i*\) 连接（`s \+ t`）[\[10\]](https://docs.python.org/3.16/library/time-complexity.html#id63) *O*\(len\(*s*\) \+ len\(*t*\)\) 重复（`s \* k`） *O*\(*nk*\) 子串搜索（`x in s`，`s\.find\(x\)`，`s\.index\(x\)`）[\[11\]](https://docs.python.org/3.16/library/time-complexity.html#id64) *O*\(*n*\) 反向子串搜索（`s\.rfind\(x\)`，`s\.rindex\(x\)`）[\[11\]](https://docs.python.org/3.16/library/time-complexity.html#id64)[\[12\]](https://docs.python.org/3.16/library/time-complexity.html#id65) *O*\(*n*× len\(*x*\)\) 编码或解码[\[13\]](https://docs.python.org/3.16/library/time-complexity.html#id66) *O*\(*n*\) 迭代 *O*\(*n*\) 获取长度（`len\(s\)`）[\[5\]](https://docs.python.org/3.16/library/time-complexity.html#id58) *O*\(1\) ## `memoryview`¶ (https://docs.python.org/3.16/library/time-complexity.html#memoryview) `memoryview` (https://docs.python.org/3.16/library/stdtypes.html#memoryview) 对象允许 Python 代码访问支持缓冲区协议 (https://docs.python.org/3.16/c-api/buffer.html#bufferobjects) 的对象的内部数据，而无需复制。特别是，对内存视图进行切片会返回指向同一缓冲区的新视图。 操作 复杂度 创建（`memoryview\(obj\)`） *O*\(1\) 获取元素（`v\[k\]`） *O*\(1\) 获取切片（`v\[i:j\]`） *O*\(1\) 索引（`v\.index\(x\)`）[\[11\]](https://docs.python.org/3.16/library/time-complexity.html#id64)[\[14\]](https://docs.python.org/3.16/library/time-complexity.html#id67) *O*\(*n*\) 计数（`v\.count\(x\)`）[\[14\]](https://docs.python.org/3.16/library/time-complexity.html#id67) *O*\(*n*\) 转换为字节（`v\.tobytes\(\)`，`bytes\(v\)`） *O*\(*n*\) 获取长度（`len\(v\)`）[\[5\]](https://docs.python.org/3.16/library/time-complexity.html#id58) *O*\(1\) ## `range`¶ (https://docs.python.org/3.16/library/time-complexity.html#range) `range` (https://docs.python.org/3.16/library/stdtypes.html#range) 对象根据其 *start*、*stop* 和 *step* 值按需计算其元素，因此大多数操作不依赖于范围的长度。 操作 复杂度 获取元素（`r\[k\]`） *O*\(1\) 获取切片（`r\[i:j\]`） *O*\(1\) `x in r`[\[15\]](https://docs.python.org/3.16/library/time-complexity.html#id68) *O*\(1\) 索引和计数（`r\.index\(x\)`，`r\.count\(x\)`）[\[15\]](https://docs.python.org/3.16/library/time-complexity.html#id68) *O*\(1\) 迭代 *O*\(*n*\) `min\(r\)`，`max\(r\)` *O*\(*n*\) 获取长度（`len\(r\)`）[\[5\]](https://docs.python.org/3.16/library/time-complexity.html#id58) *O*\(1\) ## 注释¶ (https://docs.python.org/3.16/library/time-complexity.html#notes)