第14章+：摊还分析（可选深入）

Vol 2：算法森林探险 · 第14+站（下）：账本里的秘密

---

你在哪

森林深处有一本古老的账本，记录着另一种智慧：有些操作偶尔很贵，但平均下来却很便宜——这就是摊还分析。

上一站你在"复杂度暗区"看完了 NP-complete——那是一个"有些问题根本没法快"的世界。

但这章的主角恰好相反：有些操作最坏情况很慢，但你把它放在更大的时间窗口里看——其实很快。

从你每天都在用的动态数组（list.append 平均 O(1)），到你见过但没深究的 splay 树——它们都属于"偶尔跪一次，但大部分时间都在快跑"的结构。

摊还分析就是解释这种现象的数学工具。它不矫正复杂度。它告诉你：有些最坏情况分析太悲观了。真实世界应该看平均。

---

📌 本章为可选深入，不影响主线。 如果你只是想学常规的算法面试内容，跳过本章完全没问题。

你的任务

本章分层

• 必读（如果你想看）：动态数组扩容时的摊还分析——用这个例子理解"偶尔慢一次但整体快"的概念
• 选读：聚合分析法（总代价/操作次数）
• 深水区：记账法和势能法的数学推导；splay 树的摊还分析

本章不会要求你掌握

• 势能法的严格数学证明
• splay 树的全部旋转细节

学完这一章，你要做到以下四件事：

1. 理解摊还分析为什么比最坏情况更准确地刻画某些数据结构
2. 会用聚合分析和记账法分析简单场景
3. 能解释动态数组的 push_back 为什么是"摊销 O(1)"——这是你每天都在用的
4. 了解 splay 树的复杂度是摊销 O(log n)

---

遭遇战：一个物资记录的偶发延迟

你负责记录森林驿站每天的物资清单。每秒几十批物资进出，全部写入你的冒险者笔记（一个动态数组）。然后驿站长老说——"昨晚有一次记录花了 200 毫秒才写进去，你查查笔记。"

你翻了翻笔记的实现，发现就是一行：

# 你写的物资记录系统
class SupplyLog:
    def __init__(self):
        self.log = []          # 动态数组
        self.write_count = 0

    def append(self, record):
        self.log.append(record)  # 大部分时候很快
        self.write_count += 1

    def size(self):
        return len(self.log)

看上去人畜无害。但为什么某次写入花了 200ms？

答案在 Python 的 list.append 内部。动态数组满了之后，需要：

1. 分配一块更大的空间（通常是当前大小的 2 倍）
2. 把所有旧记录誊抄过去
3. 腾出旧空间

你要誊抄 10 万条记录 每条几微秒 ≈ 几百毫秒。 这就是那夜的神秘延时。

问题是——你不能因为这个"偶尔慢一次"就抛弃动态数组。 因为大多数 append 都是 O(1) 的。你需要一种工具来回答：

动态数组的 append，平均下来到底是多少？

答案：摊销 O(1)。

我们来算：

如果初始容量是 1，每次翻倍，插入 n 个元素：

• 第 1 次插入：1 次写入（无誊抄）
• 第 2 次插入：1 次写入 + 誊抄 1 个
• 第 3、4 次插入：写入 2 次 + 誊抄 2 个
• ...

n 次插入的总代价 ≈ n + (1 + 2 + 4 + ... + n/2) = n + (n - 1) ≈ 2n

平均每次 = 2n/n = O(1)。

这一次说服了驿站长老："不是笔记有问题，是摊还。200ms 之前和之后的 99 次记录都是 O(1)，这次对冲掉这段时间的总 O(n)。"

** Java 差异：** Java 的 ArrayList 默认初始容量是 10，扩容因子 1.5 倍（而非 Python/C++ 的 2 倍）。摊还分析结果是一样的 O(1)，但 1.5 倍扩容更节省内存，代价是更多次扩容。系数上 2 倍的总拷贝量约为 O(n)，1.5 倍的总拷贝量约为 O(k·n)（k≈2.5）。语言层常数差异不改变摊还结论。

** C++ 差异：** C++ 的 std::vector 默认扩容因子一般是 2（不同实现不同，GCC/libstdc++ 用 2，MSVC 用 1.5）。C++ 的一个关键差异是：如果你存的是非平凡对象（有析构函数），扩容时调用的是 move 构造或拷贝构造，而不是 memcpy。这意味着拷贝成本比 Python 的指针数组更高。但摊还 O(1) 不变。

---

常见陷阱：三种摊还分析方法

方法 1: 聚合分析（Aggregate Analysis）

最简单直接：把所有操作的总代价加起来，除以操作次数。

# 演示：动态数组的聚合分析
def amortized_dynamic_array(n):
    """
    模拟动态数组的 push_back + 扩容
    记录每次操作的代价（复制元素代价 = 1 每个元素）
    计算摊还成本
    """
    arr = [None]   # 初始容量 1
    capacity = 1
    total_cost = 0

    for i in range(1, n + 1):
        if len(arr) == capacity:   # 满了，扩容
            new_capacity = capacity * 2
            new_arr = [None] * new_capacity
            for j in range(capacity):
                new_arr[j] = arr[j]   # 拷贝
                total_cost += 1
            capacity = new_capacity
            arr = new_arr
        arr[len(arr)] = i   # 写入当前元素
        total_cost += 1
        if i == 1 or i == n or i == n // 2:
            print(f"插入第 {i} 个元素后: 总代价={total_cost}, 均摊={total_cost/i:.2f}")

amortized_dynamic_array(16)

输出预期：

插入第 1 个元素后: 总代价=1, 均摊=1.00
插入第 8 个元素后: 总代价=21, 均摊=2.62
插入第 16 个元素后: 总代价=49, 均摊=3.06

随着 n 增大，均摊成本稳定在 O(1)。你可以看到它靠近 3 附近——因为每次扩容拷贝 + 写入的极限总代价是 2n + (n-1) ≈ 3n。

但是： 聚合分析太笼统了。它只说"平均是多少"，却不告诉你"哪些操作贵，哪些便宜"。下面两种方法给你更精细的视角。

方法 2: 记账法（Accounting Method）

核心理念：提前收费，延迟消费。

每个操作被赋予一个"摊还代价"（可能大于实际代价）。多出来的部分存到"信用"账户里，供高成本操作日后使用。

关键是： 信用账户余额永远不能为负。这意味着你提前收取的费用足够覆盖未来的成本。

# 记账法模拟：动态数组
def accounting_dynamic_array(n):
    """
    摊还代价 = 3（每个插入预先支付 3 个信用）
    实际代价 = 1（普通插入）或 capacity（扩容拷贝）
    信用 = 摊还 - 实际
    """
    capacity = 1
    balance = 0  # 信用账户

    for i in range(1, n + 1):
        amortized_charge = 3  # 每次插入统一收 3

        if i > capacity:   # 需要扩容
            copy_cost = capacity   # 把 size 个旧元素拷走
            actual_cost = copy_cost + 1  # 拷贝 + 新元素写入
            capacity *= 2
        else:
            actual_cost = 1  # 普通写入

        balance += amortized_charge - actual_cost

        if i in [1, 2, 3, 4, 8, 16]:
            print(f"  i={i:2d}: 实际={actual_cost:2d}, 摊销={amortized_charge}, "
                  f"差额={amortized_charge - actual_cost:3d}, 余额={balance:3d}")

    print(f"  n={n}: 最终余额={balance}（应 ≥ 0）")

print("记账法分析动态数组:")
accounting_dynamic_array(16)

输出预期：

记账法分析动态数组:
  i= 1: 实际= 1, 摊销=3, 差额= 2, 余额= 2
  i= 2: 实际= 2, 摊销=3, 差额= 1, 余额= 3
  i= 3: 实际= 1, 摊销=3, 差额= 2, 余额= 5
  i= 4: 实际= 4, 摊销=3, 差额=-1, 余额= 4
  i= 8: 实际= 5, 摊销=3, 差额=-2, 余额= 3
  i=16: 实际= 6, 摊销=3, 差额=-3, 余额= 3

看到了吗？每次普通插入（实际代价=1）预存 2 到余额。扩容时（实际代价=capacity 或更多），余额被花掉。余额始终为正——证明摊还代价=3 是安全的。

📌 为什么是 3？ 因为每次扩容你拷贝了 capacity 个老元素，而且每个老元素在它被写入时收过 1 个信用，扩容后还要再收一次用来覆盖这个拷贝。对新元素的最后一个拷贝——总共 3：一次写（当前写入），一次未来拷贝（扩容时搬走），一次"提前存"。

势能法（Potential Method）——深水区

势能法是三种方法中最数学化的一个。 主线只需要用动态数组的例子理解摊还概念即可。势能法和 splay 树分析属于深水区。

势能法比记账法更数学化。它定义一个"势能函数" Φ(Dᵢ) 来描述数据结构在状态 i 的状态。

摊还代价 = 实际代价 + Φ(Dᵢ) - Φ(Dᵢ₋₁)

如果势能定义为："当前容量中未使用的空间的数量"或"已经存了信用但还没花的潜在工作"。

对动态数组，典型的势能函数是：

Φ(arr) = |2 * size - capacity|  如果 size ≥ capacity/2
       = capacity/2 - size       如果 size < capacity/2

但大多数教学出于简洁，直接用：

Φ(arr) = 2 * size - capacity   （在 size ≥ capacity/2 时）

我们来计算：

操作前: size = k, capacity = 2k, Φ = 2k - 2k = 0
操作: 插入一个元素，size → k+1
情况1: 不扩容（k < capacity）→ 实际代价 = 1
  Φ_new = 2(k+1) - 2k = 2
  摊还代价 = 1 + (2 - 0) = 3

情况2: 扩容（k = capacity）→ 拷贝 cost = k, 插入 cost = 1, 新 capacity = 2k
  Φ_old = 2k - k = k   # 容量刚满时势能
  size_new = k+1, 新容量 = 2k
  Φ_new = 2(k+1) - 2k = 2
  摊还代价 = (k+1) + (2 - k) = 3

一模一样。势能法告诉你——无论扩容还是不扩容，摊还代价都是 3。

def potential_dynamic_array(n):
    """势能法验证"""
    size = 0
    capacity = 1
    potential = 0
    total_amortized = 0

    for i in range(1, n + 1):
        prev_phi = potential

        if size == capacity:
            # 扩容
            actual = capacity + 1
            new_capacity = capacity * 2
            phi_after = 2 * (size + 1) - new_capacity  # 扩容后
        else:
            actual = 1
            phi_after = 2 * (size + 1) - capacity

        potential = phi_after
        amortized = actual + (potential - prev_phi)
        total_amortized += amortized

        size += 1
        if size <= 5 or size == n:
            print(f"  size={size:2d}:实际={actual},势能={potential:2d},ΔΦ={potential-prev_phi:2d},摊还={amortized}")

    print(f"  总摊还={total_amortized}, 等于 {total_amortized/size:.1f} × n")

print("势能法分析动态数组:")
potential_dynamic_array(16)

三个案例：看透摊销的场景

案例 1: 二进制计数器（Binary Counter）

# 二进制计数器递增 —— 分析翻转次数
def count_bit_flips(n):
    """
    从 0 递增到 n，统计二进制位的翻转次数
    直观：k 位全翻转只发生一次（最高位），但很多低位的翻转次数很少
    """
    total_flips = 0
    for i in range(1, n + 1):
        # i 的二进制表示中，有多少个尾部连续的 1 就要翻转多少位
        flips = (i & -i).bit_length()  # 低位连续 1 的个数
        total_flips += flips
    return total_flips

for n in [1, 2, 4, 8, 16, 32, 64, 128]:
    flips = count_bit_flips(n)
    print(f"n={n:4d}: 总翻转={flips:5d}, 均摊/位={flips/n:.4f}")

输出：

n=   1: 总翻转=    1, 均摊/位=1.0000
n=   2: 总翻转=    3, 均摊/位=1.5000
n=   4: 总翻转=    7, 均摊/位=1.7500
n=   8: 总翻转=   15, 均摊/位=1.8750
n=  16: 总翻转=   31, 均摊/位=1.9375
n=  32: 总翻转=   63, 均摊/位=1.9688
n=  64: 总翻转=  127, 均摊/位=1.9844
n= 128: 总翻转=  255, 均摊/位=1.9922

聚合分析： 总翻转次数永远 = 2n - 1，所以摊还 = 2 - 1/n = O(1)。

势能法： 定义势能 = 计数器中 1 的个数。递增时，低位 k 个 1 变 0（势能减 k），一个 0 变 1（势能加 1）。ΔΦ = (1-k)，实际代价 = k+1（k 次翻转 + 1 次置位），摊还 = (k+1) + (1-k) = 2。永远等于 2。

案例 2: 并查集（Union-Find）的路径压缩

# 简化版并查集 —— 展示路径压缩的摊销效果
class DisjointSet:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [0] * n
        self.find_count = 0

    def find(self, x):
        """路径压缩 find —— 摊还 O(α(n))"""
        self.find_count += 1
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]

    def union(self, x, y):
        """按秩合并"""
        rx, ry = self.find(x), self.find(y)
        if rx == ry:
            return
        if self.rank[rx] < self.rank[ry]:
            self.parent[rx] = ry
        elif self.rank[rx] > self.rank[ry]:
            self.parent[ry] = rx
        else:
            self.parent[ry] = rx
            self.rank[rx] += 1

# 测试：100k 次操作的平均 find 代价
import random
ds = DisjointSet(10000)
ops = 0
for _ in range(5000):
    a, b = random.randint(0, 9999), random.randint(0, 9999)
    ds.union(a, b)
for _ in range(5000):
    _ = ds.find(random.randint(0, 9999))
print(f"总 find 递归调用次数: {ds.find_count}")
print(f"平均每次 find 的路径: {ds.find_count / 5000:.2f}")
# 预期输出：远小于 log₂n（≈14），可能只有 5 左右

并查集的摊还复杂度极其优秀——几乎是常数（逆阿克曼函数 α(n)）。 在实际中 n ≤ 10⁶ 时 α(n) ≤ 4。

案例 3: splay 树的摊还分析（概念 + 代码片段）

splay 树的摊还分析属于深水区。 知道"splay 树通过自调整实现摊销 O(log n)"这个结论即可。

splay 树是一种自调整的二叉搜索树。每次访问一个节点，把它旋转到根。最近访问的节点下次更快访问。

初始:         访问 4 后:        访问 8 后:
    7             4                 8
   / \             \               /
  4   9             7             4
 / \               / \             \
2   6             2   6            7
                 /                /
                1                2
                                  \
                                   6

splay 树的摊还证明用势能法——势能定义为各节点子树大小的对数之和（秩的和）。

Φ(T) = Σ log₂(size(x))
       x∈T

证明的核心：

• 访问操作的摊还代价 = O(log n)，因为访问一个节点到根的过程中，旋转操作引起的势能变化抵消了大部分实际代价。
• 更深入的推导显示：一次 splay 的实际代价 ≤ 3 · (rank(root) - rank(target)) + 1 = O(log n)。

# 概念演示：splay 树的摊还逻辑
class SplayNode:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None

# 省略完整 splay 实现（书籍篇幅有限）
# 关键结论：m 次操作（查找/插入/删除）的总时间 = O(m log n)
# 即使最坏的单次操作 O(n)，m 次加起来最多 O(m log n)

** Java 差异：** Java 标准库未提供 splay 树实现。但 TreeMap（红黑树）是严格的 O(log n) 每次操作，而 splay 树只有摊还的 O(log n)。分布式系统中 splay 树的价值在于"热点数据自动提升"——不用手动调优缓存策略。

** C++ 差异：** C++ 标准库也没有 splay 树（std::set 和 std::map 是红黑树）。但 splay 树在实现时要注意指针管理——C++ 中 splay 的旋转操作涉及大量指针重连，容易写出 bug。建议用智能指针或裸指针+封装。

---

通关挑战

1. 势能法推导：栈的多重操作 设计一个栈，支持 push（O(1)）和 multipop(k)（弹出 k 个元素，O(k)），外加一个 increment() 操作（把栈顶 k 个元素均 +1，消耗 O(k) 时间）。用势能法证明所有操作的摊还代价为 O(1)。提示：势能 = 栈中元素数量。

2. 记账法证明二进制计数器摊销 O(1) 给二进制计数器的递增操作定义一个摊还代价为 2。精确列出前 8 次递增的"实际代价"和"信用余额"。证明余额始终非负。

3. splay 树的最坏情况例子 构造一个 splay 树，使其每次访问都触发最坏 O(n) 的实际操作。提示：按升序访问节点。

👆 参考答案

1. 势能 Φ = 栈的大小。push：实际=1，ΔΦ=+1，摊销=2。multipop(k)：实际=k，ΔΦ=-k，摊销=k+(-k)=0。increment(对顶 k 个元素)：虽然实际=O(k)，但这些元素被 increment 后留在栈中——势能不变，但更精确的势能可能需要重新定义。一个更巧的势能是：栈中元素的值之和——这样 increment 增加了势能，抵消了 O(k) 的实际代价。摊销 = O(1)。

2. 摊还代价 = 2。信用规则：第 0→1 位每次从 0→1 时存 1，1→0 时花 1。第 1→2 位存 2 花 2... 但更简单的：设计数器有 1 的 k 个位，每次递增恰好把 k 个 1 变 0 加 1 个 0 变 1。摊还 2 = (k+1) + (-k+1) 的正值覆盖。

3. 在初始有序树（退化为链表）中按升序访问每个节点。第一次访问最小编号节点 splay 到根——遍历整条链（O(n)）。每次后续访问也是 O(当前节点到根的距离)，总体仍摊销 O(log n) 每次。纯最坏构造需要不断插入-访问-插入-访问的交替模式。

---

验收标准

读完本章后，你能：

• [ ] 用自己的话解释"摊还 O(1)"和最坏情况 O(1) 的差别
• [ ] 用三种方法（聚合/记账/势能）分析动态数组的摊销
• [ ] 解释二进制计数器为什么是摊销 O(1) 不是 O(k)
• [ ] 在面试或代码审查中识别出"这个操作是摊销 O(1)，不是最坏 O(1)"
• [ ] 理解 splay 树为什么值得学——不需要记住旋转细节，但要知道它的摊还特性和应用场景

---

常见卡点

卡点	真相
"摊还 = 平均情况下分析"	不。摊还是对全部操作取平均，不是"平均输入分布"。最坏输入的序列也要满足摊还界
"摊还 O(1) = 每次操作都是 O(1)"	错。摊还 O(1) 意味着某些操作可能很慢，但慢的次数被快的次数稀释了
"记账法的信用值随便定"	信用必须在数学上证明永远不会为负。不是感情上的"我觉得够用"
"摊还分析只在理论上重要"	实战极有用——动态数组就是你每天都在用的数据结构。理解摊还 = 理解你的 push_back 为什么"偶尔慢但整体快"
"势能函数很难选"	入门级用例有一个通用策略：势能 = 数据结构的"混乱程度"或"待完成工作量"。动态数组用"容量-大小"，并查集用"路径长度"，splay 树用"秩"

---

现在不需要理解

• splay 树的全部旋转细节——知道"自调整树靠旋转维持摊还界"就够。完整实现太长，需要时查资料就行
• 逆阿克曼函数 α(n) 的严格推导——知道它是"增长极慢的函数"就够了。α(10⁶) ≤ 4，α(宇宙原子数) ≤ 5
• 斐波那契堆的摊还分析——比 splay 树复杂很多。第15章（高级数据结构）会涉及
• 摊还分析的竞赛级技巧——ACM/ICPC 里有更复杂的势能构造，但不是所有人需要

---

旅人笔记

• 摊还是你能讲给产品经理听的复杂度分析。 你说"最坏情况 200ms"他们慌张，你说"平均每次 1μs"他们安心。摊还帮你把故事讲好——数据是对的，故事也是真的。
• 动态数组的扩容因子不是 2 就是 1.5。 选 2：拷贝更少（均摊≈3），但内存浪费更多（最多 100% 空闲）。选 1.5：拷贝稍多（均摊≈5），但内存回收更快。Python 选 1.125（从 PyPy 开始）——更激进的内存节省策略。
• 面试中摊还分析出现频率比你想象的低。 但你只要能流利解释"为什么 ArrayList 的 add 是 O(1)"，面试官就知道你不仅会用，还懂原理。
• 把摊还看作"工程优化的通用语言"。 批处理操作（bulk load）、缓存失效、垃圾回收——都能用摊还视角理解。"偶尔做一次重活，平时轻松干活"是计算机系统里一个反复出现的模式。
• 摊还分析 vs 平均情况分析的区别： 摊还不对输入做概率假设。它说"最恶心的操作序列来了也跑不掉"——上限是硬的。

---

摊还分析速查表

数据结构 / 操作	摊还代价	方法
动态数组 push_back	O(1)	聚合/记账/势能
二进制计数器 INCREMENT	O(1)	聚合（总翻转=2n-1）
并查集 find（路径压缩+按秩合并）	O(α(n))	势能法（需多层势能）
splay 树查找/插入/删除	O(log n)	势能法（秩的和）
栈的多重弹出 multipop	O(1)	势能法（Φ=栈大小）
二项堆 merge	O(log n)	势能法（Φ=树的数量）

---

→ 下一站预告

第15章（可选）：高级数据结构

你把摊还分析——这个"看似短跑，实则马拉松"的复杂度视角——彻底吃透了。

下一站，我们拿着这把新武器去面对更复杂的数据结构：斐波那契堆、van Emde Boas 树、后缀数组。每一块都有自己的摊还故事。