内置对象的复杂度
Python 无需导入即可使用的一切：内置类型、内置函数、常量以及异常体系。下面每一项都链接到
给出完整分析的页面；本页的表格给出主要复杂度，便于一眼找到所需内容。
内置类型
| 类型 |
适用场景 |
平均访问 |
平均插入 |
平均删除 |
list |
有序序列 |
O(1) |
O(n) |
O(n) |
tuple |
不可变序列 |
O(1) |
- |
- |
range |
数值序列 |
O(1) |
- |
- |
str |
文本 |
O(1) |
- |
- |
bytes |
二进制数据 |
O(1) |
- |
- |
dict |
键值映射 |
O(1) |
O(1) |
O(1) |
set |
唯一元素 |
- |
O(1) |
O(1) |
frozendict |
不可变的键值映射（3.15+） |
O(1) |
- |
- |
frozenset |
不可变的唯一元素 |
- |
- |
- |
序列类型
- 列表 - 最灵活的序列类型
- 元组 - 不可变序列
- 范围 - 惰性求值的数值序列
- 字符串 - 文本与字符序列
- 字节 - 不可变的二进制数据
- 字节数组 - 可变的二进制数据，原地修改
映射与集合类型
数值与布尔类型
- 整数 - 任意精度整数
- 浮点数 - IEEE 754 双精度
- 布尔值 - 两个单例，
int 的子类
内置函数
迭代
这一组函数返回迭代器。创建迭代器的开销很小；备注列中给出的开销是消耗该迭代器所需付出的代价。
| 函数 |
时间 |
空间 |
备注 |
iter() |
O(1) |
O(1) |
把可迭代对象包装成迭代器 |
next() |
O(1)* |
O(1) |
* 开销取决于底层迭代器 |
aiter() |
O(1) |
O(1) |
iter() 的异步版本 |
anext() |
O(1) |
O(1) |
await 的开销即异步生成器本身的开销 |
enumerate() |
O(1) |
O(1) |
消耗为 O(n)；产出 (索引, 元素) 元组 |
zip() |
O(1) |
O(1) |
消耗为 O(n)；在最短的可迭代对象处停止 |
map() |
O(1) |
O(1) |
消耗为 O(n*k)，k 为函数耗时 |
filter() |
O(1) |
O(1) |
消耗为 O(n*k)，k 为谓词耗时 |
reversed() |
O(1) |
O(1) |
消耗为 O(n)；需要 __reversed__ 或 __getitem__ |
聚合与排序
| 函数 |
时间 |
空间 |
备注 |
len() |
O(1) |
O(1) |
内置容器会缓存自身长度 |
sum() |
O(n) |
O(1) |
若误用于拼接字符串则为 O(n²) |
min() |
O(n) |
O(1) |
必须比较每个元素 |
max() |
O(n) |
O(1) |
必须比较每个元素 |
sorted() |
O(n log n) |
O(n) |
Powersort |
all() |
O(n) |
O(1) |
遇到第一个假值即短路 |
any() |
O(n) |
O(1) |
遇到第一个真值即短路 |
数值与进制
| 函数 |
时间 |
空间 |
备注 |
abs() |
O(1) |
O(1) |
n 位负 int 为 O(n)；自定义 __abs__() 的成本由其实现决定 |
divmod() |
O(1) |
O(1) |
任意精度整数为 O(n²) |
pow() |
O(r²) |
Θ(r) |
r 为结果的位数；三参数形式为 O(log y * m²)，空间 Θ(m) |
round() |
O(1) |
O(1) |
恰为一半时采用银行家舍入 |
bin() |
O(log n) |
O(log n) |
开销即输出的长度 |
hex() |
O(log n) |
O(log n) |
开销即输出的长度 |
oct() |
O(log n) |
O(log n) |
开销即输出的长度 |
文本与字符
| 函数 |
时间 |
空间 |
备注 |
chr() |
O(1) |
O(1) |
码位转字符 |
ord() |
O(1) |
O(1) |
字符转码位 |
format() |
O(n) |
O(n + p) |
n 为结果长度，p 为精度；十进制 int 与 str() 一样为 O(n²)，既不填充也不截断的精确 str 为 O(1) |
repr() |
O(n) |
O(n) |
递归处理容器 |
ascii() |
O(n) |
O(n) |
与 repr() 类似，但转义非 ASCII 字符 |
hash() |
O(k) |
O(1) |
k 为内置类型值的大小，或其 __hash__ 的开销；str、bytes 和 frozenset 会保存结果，元组从 3.14 起也会 |
对象、属性与类型
类型构造器
| 构造器 |
时间 |
空间 |
备注 |
bool() |
O(1) |
O(1) |
容器通过 __len__() 判断，该操作为 O(1) |
int() |
O(1) |
O(1) |
解析很长的数字字符串时为 O(n²) |
float() |
O(1) |
O(1) |
从字符串转换为 O(n)，含非 ASCII 字符或下划线时空间也为 O(n)；从 d 位整数转换最坏为 O(d) |
complex() |
O(1) |
O(1) |
从字符串转换为 O(n) |
str() |
O(1) |
O(1) |
容器与自定义 __str__() 为 O(n) |
bytes() |
O(n) |
O(n) |
n 为来源的长度；来源的类型恰为 bytes 时为 O(1) |
bytearray() |
O(n) |
O(n) |
n 为来源的长度 |
memoryview() |
O(1) |
O(1) |
缓冲区上的视图，从不复制 |
list() |
O(n) |
O(n) |
n 为可迭代对象的长度 |
tuple() |
O(n) |
O(n) |
参数已经是元组时为 O(1) |
dict() |
O(n) |
O(n) |
哈希冲突下最坏为 O(n²) |
set() |
O(n) |
O(n) |
哈希冲突下最坏为 O(n²) |
frozenset() |
O(n) |
O(n) |
参数已经是 frozenset 时为 O(1) |
slice() |
O(1) |
O(1) |
只保存索引；实际应用时为 O(k) |
object() |
O(1) |
O(1) |
所有类的基类 |
sentinel() |
O(1) |
O(1) |
Python 3.15+；唯一的具名标记值，用 is 比较 |
代码执行
| 函数 |
时间 |
空间 |
备注 |
eval() |
O(n + m) |
O(n + m) |
n 为源码长度，m 为求值开销 |
exec() |
O(n + m) |
O(n + m) |
n 为源码长度，m 为执行开销 |
compile() |
O(n) |
O(n) |
解析加上字节码生成 |
globals() |
O(1) |
O(1) |
返回已存在的模块字典 |
locals() |
O(1) |
O(1) |
在优化过的函数作用域中为 O(m) |
输入、输出与调试
| 函数 |
时间 |
空间 |
备注 |
print() |
O(n) |
O(n) |
n 为输出总长度；开销以 I/O 为主 |
input() |
O(k) |
O(k) |
k 为读取行的长度 |
open() |
O(1)* |
O(1) |
* 系统调用；读写的开销取决于数据量 |
help() |
O(D) |
O(D) |
D 为为该对象生成文档的开销，页面按对象种类分别给出 |
breakpoint() |
O(1) |
O(1) |
把控制权交给调试器 |
常量
异常与解释器
核心概念
均摊复杂度
某些操作（如 list.append()）具有均摊 O(1) 复杂度，这意味着：
- 大多数追加操作是 O(1)
- 偶尔会触发一次需要 O(n) 的扩容
- 在大量操作上平均下来是 O(1)
惰性与急切
有几个内置函数返回的是迭代器而不是结果。无论输入多大，调用它们都是 O(1)；真正的工作发生在
消耗迭代器的过程中，被跳过的元素则完全不会产生开销。用 list() 包裹调用会让它重新变为急切
求值，并恢复 O(n) 的空间开销。
实现细节
CPython 使用：
- 列表：带超额分配的动态数组
- 字典：采用开放寻址的哈希表
- 集合：哈希表（与字典类似）
版本说明
不同 Python 版本各有优化：
- Python 3.7+：字典的插入顺序得到保证（语言规范）
- Python 3.9+：新的字典实现带来改进
- Python 3.10+：对常见操作的进一步优化
按版本查看详细变更日志，请参见版本。
另请参阅