复杂度、资源成本与实测
本节目标
用 Big O 描述输入变大时资源成本怎样增长，区分最坏、平均与摊还复杂度，并通过可复现实测验证趋势而不是制造通用性能数字。
复杂度属于操作，不属于容器名字
回到 ADT 与不变量 写出的操作画像。选择结构前先问：
- 需要按位置访问，还是按唯一 ID 查找？
- 需要保持顺序、允许重复吗？
- 最常见的是尾部追加、头部取出，还是任意位置插入？
- 是否需要优先取出“最紧急”的元素？
- 数据之间是否有父子或依赖关系？
“使用列表”不能单独得到一个复杂度；items[i]、value in items、append 和 pop(0) 是不同操作。分析还必须说明输入规模 代表任务数、节点数、边数还是文本长度。
Big O 是增长趋势，不是秒表
设输入规模为 ：
- ：成本不随 成比例增长，例如按列表下标读取。
- ：每一步大幅缩小问题，例如平衡搜索结构或堆操作的层数。
- ：元素增加一倍，工作量大致也增加一倍，例如扫描列表。
- ：常见高效比较排序的量级。
- ：两层遍历所有元素对，数据大时增长很快。
Big O 忽略常数和较低阶项，用于比较规模扩大后的趋势。它不代表实际时间，也不说明网络、磁盘、内存和实现常数。小数据上，清晰正确通常比微小性能差异重要。
最坏、平均与摊还
- 最坏情况：在允许输入中成本最高的一种；
- 平均情况：需要明确输入分布或实现假设，不能把“通常”当证明；
- 摊还成本：一串操作的总成本平均到每次，例如动态数组偶尔扩容，但连续尾部追加通常为摊还 。
字典/集合成员测试常按平均 建模；这不是最坏情况或安全保证。若输入可被攻击者控制，还要考虑哈希碰撞、资源上限和实现防护。
同一需求的两种写法
检查一批 run_id 是否已处理：
processed_list = ["r1", "r2", "r3"]
print("r3" in processed_list) # 最坏要扫描列表，O(n)
processed_set = {"r1", "r2", "r3"}
print("r3" in processed_set) # 平均 O(1)集合更适合频繁成员测试，但它不是“有顺序的历史记录”。如果既要保留处理顺序又要快速去重，可以同时维护列表和集合，但必须封装更新，避免两者不一致。
常见 Python 操作的直觉成本
| 操作 | 常见结构 | 典型复杂度 | 原因直觉 |
|---|---|---|---|
| 按下标读取 | list | 可直接定位槽位 | |
| 在列表中找值 | list | 可能逐个比较 | |
| 尾部追加 | list.append | 摊还 | 偶尔扩容，平均到多次操作 |
| 头部删除 | list.pop(0) | 后续元素需要移动 | |
| 队首弹出 | deque.popleft | 两端操作为设计目标 | |
| 按键查找 | dict | 平均 | 使用哈希定位 |
| 集合成员测试 | set | 平均 | 同样基于哈希 |
| 堆压入/弹出 | heapq | 沿树高恢复堆序 |
“平均”不等于无条件保证；哈希冲突、内存压力和恶意输入都会影响实际表现。
这张表描述 Python/常见 CPython 实现的实用成本模型，并由官方文档和算法资料支持；它不是所有 Python 实现必须逐项满足的语言级时间保证。版本、数据类型和硬件变化时应重新测量。
空间成本与峰值内存
时间快不代表内存小。考虑：
- 输入本身、辅助索引和输出各占多少随规模增长的空间；
- 容器通常保存对象引用，浅拷贝不会递归复制引用对象；
- 生成器若被立即
list(...)，仍会物化全部结果； - 同时保留
list+set可换取更快成员测试，但增加 辅助空间和一致性不变量。
sys.getsizeof() 只报告对象直接占用，不递归统计它引用的对象。测一段真实 Python 分配可用 tracemalloc，但结果仍与版本和运行环境相关。
用 timeit 验证趋势
下面只比较同一台机器、同一解释器上的增长趋势：
from timeit import timeit
def compare_membership(size: int) -> tuple[float, float]:
values = list(range(size))
value_set = set(values)
target = size - 1
list_seconds = timeit(lambda: target in values, number=2_000)
set_seconds = timeit(lambda: target in value_set, number=2_000)
return list_seconds, set_seconds
for n in (100, 1_000, 10_000):
print(n, compare_membership(n))记录 Python 版本、数据规模、重复次数和数据分布。不要把一次笔记本结果写成“列表总是慢 X 倍”；测量可能受缓存、启动、后台负载和被测对象哈希成本影响。
最小内存测量：
import tracemalloc
tracemalloc.start()
values = [str(i) for i in range(10_000)]
current, peak = tracemalloc.get_traced_memory()
print({"current_bytes": current, "peak_bytes": peak})
tracemalloc.stop()这只观察跟踪期间 Python 分配，不等于进程全部内存或跨版本固定结果。tracemalloc 本身也有 CPU/内存开销；比较前后要使用相同配置和工作负载。
Agent 工程中的选择
- 消息按时间追加与遍历：
list。 - 最近 N 条事件：
deque(maxlen=N)。 tool_name → tool_definition：dict。- 已处理事件 ID：
set。 - 下一项按优先级取出：
heapq。 - 步骤依赖：图的邻接表
dict[str, set[str]]。
结构不能替代业务规则。集合能发现重复 ID，但不能判断两次请求在业务上是否等价；这需要幂等键和明确语义。
练习
为以下需求选择结构并解释主要操作：
- 保存对话消息并按原顺序发送给模型。
- 只保留最近 100 条延迟样本。
- 按工具名快速获取参数 schema。
- 每次取出最高优先级、最早进入的任务。
- 判断任务之间是否存在循环依赖。
再运行上述 timeit，只回答：随着 从 100 增到 10,000，两条曲线的增长趋势是否符合模型？保留原始输出、解释器版本和任何反常现象。
自测
- 是否表示“只需一条机器指令”？
- 为什么
list.pop(0)不适合大队列？ - “摊还 ”中的摊还是什么意思？
- 为什么复杂度相同的两个方案仍可能有明显速度差异？
sys.getsizeof(container)为什么不等于整棵嵌套对象的总内存？- “字典查找是 O(1)”还缺少哪个情况限定？
参考答案： 只表示成本不按输入规模增长；列表头部删除要移动后续元素；偶发高成本被分摊到一系列操作；实现常数、缓存、内存、I/O 和数据分布都会影响实测；getsizeof 不递归统计被引用对象；字典成员测试通常说的是平均成本且依赖实现/输入假设。
下一步与相关概念
下一节：顺序、链式与二分查找。
参考资料
获取日期：2026-07-14。