2.9 摊还分析
学习目标
学完这一节，你能：
- 解释摊还分析研究的是一串操作的总代价
- 区分摊还分析、平均情况和期望情况
- 用动态数组扩容解释
append为什么是摊还Θ(1) - 识别 agent 对摊还复杂度的常见误解
- 用简单求和说明偶尔昂贵的操作如何被分摊
偶尔很贵，不等于整体很贵
前面说过，Python list.append(x) 是摊还 Θ(1)。
为什么不是严格 Θ(1)？
因为动态数组容量不够时，需要：
- 申请更大的空间。
- 把旧元素搬过去。
- 再加入新元素。
这一次操作可能是 Θ(n)。
但如果你连续追加很多次，大多数追加都只是放到末尾，只有少数几次触发扩容。摊还分析要问的是：
一串操作总共花了多少成本？平均分到每次操作上是多少？
形式化一点说
假设一串操作共有 m 次，第 i 次真实成本是 c_i。总成本是：
C = c_1 + c_2 + ... + c_m如果能证明：
C <= K · m其中 K 是常数，那么这串操作的摊还成本就是 O(1)。
注意，摊还分析不是说每个 c_i 都小。它允许某些 c_i 很大，只要总成本能被整体控制住。
生活类比：搬宿舍
假设你住的柜子满了，就换一个更大的柜子。换柜子那天很累，要把所有东西搬过去。但换完之后，接下来很多天只要把新物品放进去。
如果每多一件东西就换一次柜子，那当然很糟。
但如果每次柜子满了就换成大约两倍容量，搬家的次数就很少。
动态数组也是这个思路：不要每次只扩一点点，而是扩到更大的容量。
一个简化推导
假设动态数组容量满了就翻倍。
当容量从 1 扩到 2，需要搬 1 个元素。
从 2 扩到 4，需要搬 2 个元素。
从 4 扩到 8，需要搬 4 个元素。
如果最终插入 n 个元素，所有扩容搬运的总次数大约是：
1 + 2 + 4 + 8 + ... < 2n每次插入本身还要放入一个新元素，总共 n 次。
所以总成本小于：
n + 2n = 3n把 3n 分摊到 n 次插入上，每次就是常数级。
这就是为什么 append 的摊还复杂度是 Θ(1)。
摊还不是平均运气
摊还分析经常被 agent 说错。它不是：
因为平均情况下比较快，所以算 O(1)。摊还分析不依赖随机输入，也不说"运气好就快"。它给的是一串操作的确定性保证：
不管这一串操作具体怎么发生，总成本可以被界定。
对比一下：
| 分析方式 | 关注什么 | 是否依赖概率 |
|---|---|---|
| 最坏情况 | 单次操作最坏有多贵 | 不依赖 |
| 摊还分析 | 一串操作总成本分摊后多贵 | 不依赖 |
| 平均或期望分析 | 在某种输入分布或随机选择下的平均表现 | 依赖 |
所以，摊还 Θ(1) 不等于每次都是 Θ(1)。它的意思是：长期看，一串操作的总成本是线性的。
三种摊还证明语言
专业教材中常见三种摊还分析方法。本章先建立直觉，不要求你熟练使用全部技巧，但要知道它们在回答同一个问题。
| 方法 | 核心想法 | 适合理解 |
|---|---|---|
| 聚合分析 | 直接证明 m 次操作总成本是多少 | 动态数组扩容 |
| 记账法 | 便宜操作多收一点"预付款"，以后支付昂贵操作 | 扩容、批处理 |
| 势能法 | 给数据结构状态定义"势能"，操作改变势能 | 更复杂的动态结构 |
动态数组翻倍扩容用聚合分析已经足够：所有复制成本加起来小于线性倍数。
记账法可以这样想：每次 append 不只为自己付费，还预存一点信用。等到扩容需要复制旧元素时，用之前存下的信用支付。
势能法更抽象：数组还有多少空位，可以看成一种"能量"。空位多，未来扩容压力小；空位少，未来扩容压力大。操作不仅改变当前成本，也改变未来压力。
摊还分析也会失败
扩容策略如果设计不好，摊还成本可能很差。
例如，如果数组每次满了只增加 1 个位置：
容量 1 -> 2 -> 3 -> 4 -> ...第 2 次插入搬 1 个，第 3 次插入搬 2 个，第 4 次插入搬 3 个，总搬运成本是：
1 + 2 + 3 + ... + (n - 1) = Θ(n²)所以，不是所有"动态增长"都是好的。好的扩容策略通常让容量按比例增长，而不是每次只加一点。
收缩也会制造抖动
扩容不是唯一问题。缩容策略也可能出错。
假设一个动态数组：
满了就扩成两倍。
使用量低于一半就缩成一半。这听起来合理，但在临界点附近可能抖动：
插入一个元素 -> 扩容
删除一个元素 -> 缩容
再插入一个元素 -> 扩容
再删除一个元素 -> 缩容如果每次都触发大量复制，总代价就会变差。
更稳妥的策略通常会留出缓冲区，例如低于四分之一时才缩容。这样扩容线和缩容线分开，避免在边界附近来回震荡。
这个例子说明：摊还分析不只是事后解释，它也指导数据结构策略设计。
用本节知识解决：课堂问题数量突然变多
假设一开始课堂系统只有几十条问题。后来老师把它用于大型公开课，一节课可能有 5 万条问题。
如果问题记录用 Python list 保存：
questions = []
def ask(question):
questions.append(question)你可能会担心：列表容量不够时扩容不是很贵吗？
摊还分析给出的判断是：
偶尔扩容会复制旧元素；
但如果扩容按比例增长，连续很多次 append 的总成本仍然是线性的。所以，对"不断追加问题记录"这个需求，list.append 是合理的。
但如果 agent 写成这样：
def ask(question):
global questions
questions = questions + [question]情况就不同了。questions + [question] 每次都会创建新列表并复制旧内容。第 1 次复制 0 个，第 2 次复制 1 个，第 3 次复制 2 个，总成本变成：
0 + 1 + 2 + ... + (n - 1) = Θ(n²)这正好说明摊还分析的价值：它不是让你相信"动态增长都没问题"，而是帮你区分两种看起来相似的写法。
questions.append(question) # 摊还 Θ(1)
questions = questions + [question] # 每次复制，整体 Θ(n²)在 agent 时代，这类差别非常重要。两段代码都短，都能跑，但一个适合真实规模，另一个只适合小样例。
Agent 常见误解
如果 agent 写：
list.append 是 O(1)，因为它只是把元素放到末尾。
这不够准确。更专业的说法是：
append单次最坏可能触发扩容和复制，但连续多次追加的摊还复杂度是Θ(1)。
如果 agent 写：
摊还复杂度是平均情况复杂度。
这是错误的。你应该要求它重写：
请区分最坏情况、摊还情况和期望情况。
用动态数组扩容说明为什么 append 是摊还 O(1)，并说明这不依赖随机输入。和 agent 协作时怎么用摊还分析
当 agent 给出数据结构实现时，你可以要求它给出操作序列分析：
请不要只分析单次操作。
请分析连续执行 m 次操作的总成本，并说明哪些操作可能偶尔很贵。
如果使用了动态数组、哈希表扩容、缓存或批处理，请说明摊还意义。这类提示尤其适合：
- 动态数组追加
- 哈希表扩容
- 批量写入
- 缓存预处理
- 延迟删除
- 日志合并
在 agent 时代，摊还分析能帮助你识别"一次慢不代表整体慢"和"看起来每次简单但整体很慢"这两类相反的问题。
本节要点
- 摊还分析关注一串操作的总代价。
- 摊还不是平均运气，也不依赖概率假设。
- 动态数组按比例扩容时，连续
append的总成本是线性的。 - 单次操作最坏可能很贵，但摊还后每次可以是常数级。
- 审查 agent 时，要要求它说明单次最坏、摊还和期望三者的区别。
课堂练习
某 agent 解释：
Python list 的 append 永远是 O(1)，因为它只是把元素加到数组末尾。
请改写这段解释，要求包含：
- 单次最坏情况。
- 为什么扩容会复制旧元素。
- 为什么连续很多次 append 的摊还复杂度仍然是
Θ(1)。 - 为什么这不是平均情况分析。
课后测验
📝 课后测验
上一节：2.8 并查集
下一节：2.10 从接口到缓存