内置类型的复杂度

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)
frozenset	不可变的唯一元素	-	-	-

详细指南

序列类型

• 列表 - 最灵活的序列类型
• 元组 - 不可变序列
• 范围 - 惰性求值的数值序列
• 字符串 - 文本与字符序列
• 字节与字节数组 - 二进制数据与可变字节

映射与集合类型

• 字典 - 基于哈希的键值存储
• 集合 - 无序的唯一元素
• Frozenset - 不可变的唯一元素

核心概念

均摊复杂度

某些操作（如 list.append()）具有均摊 O(1) 复杂度，这意味着：

• 大多数追加操作是 O(1)
• 偶尔会触发一次需要 O(n) 的扩容
• 在大量操作上平均下来是 O(1)

实现细节

CPython 使用：

• 列表：带超额分配的动态数组
• 字典：采用开放寻址的哈希表
• 集合：哈希表（与字典类似）

版本说明

不同 Python 版本各有优化：

• Python 3.7+：字典的插入顺序得到保证（语言规范）
• Python 3.9+：新的字典实现带来改进
• Python 3.10+：对常见操作的进一步优化

按版本查看详细变更日志，请参见版本。