数据结构与算法 / 系统课时

摊还分析入门

摊还分析入门

动态数组满时,某次追加可能要复制所有旧元素。摊还分析把连续操作作为一个整体,为任意合法前缀计算总成本。它不需要假设输入或操作是随机的。 MIT 摊还分析课程资料

学习目标

  • 区分单次最坏成本、摊还成本和概率期望。
  • 对倍增数组推导任意追加前缀的总成本。
  • 用记账或势能核对扩容前后的预算。

先固定成本模型

从空数组和容量 1 开始,只执行追加。写入一个新元素计 1,复制一个旧元素也计 1。容量已满时先把容量加倍、复制旧元素,再写入新值。满数组已有 ss 个元素时,这次追加的成本是 s+1s+1,在这个状态下随 ss 线性增长。接下来只计算写入和复制,不把具体语言的内存申请与初始化计入数值。 MIT 摊还分析课程资料

动态数组扩容的摊还成本示意

聚合法:对任意前缀求和

执行 m≥1m≥1 次追加后,设最终容量为 CC。写入成本是 mm,历次复制的规模依次是 1,2,…,C/21,2,…,C/2,合计 C−1C-1。当 C=1C=1 时没有复制,同样有 C−1=0C-1=0。若发生最后一次扩容,旧容量 C/2C/2 必小于已经追加的数量 mm;若没有扩容,也满足 C<2mC<2m。所以总成本为 m+C−1<3mm+C-1<3m,同时至少为 mm。每次追加的摊还复杂度为 Θ(1)\Theta(1)。 MIT 摊还分析课程资料

不能对每个前缀都说复制次数小于 mm。前五次追加中发生了规模 1、2、4 的复制,共 7 次,总成本是 12。追加正好到 8 个时,总成本为 15。只观察容量正好用满的前缀会漏掉刚扩容的较高峰值。

记账与势能用同一个预算

记账时每次收取 3 单位,扣除实际成本后留下余额。可用势能给出这项余额的精确值。令当前元素数为 ss、容量为 CC,取 Φ=2s−C+1\Phi=2s-C+1。初始 s=0,C=1s=0,C=1,势能为 0。之后扩容刚完成时 s=C/2+1s=C/2+1,普通追加只使 ss 增加,所以势能始终非负。

对一次操作,摊还费用等于实际成本加上势能变化。普通追加的实际成本为 1,势能增加 2,合计 3。若旧容量为 CC 且已经装满,追加实际成本为 C+1C+1,新容量 2C2C、新大小 C+1C+1,势能变化为 2−C2-C,合计仍为 3。累加后中间势能项抵消,已收费用 3m3m 扣除当前势能就是实际总成本。 MIT 摊还分析课程资料

实跑扩容、计费与前缀

保存为 amortized_dynamic_array.py,用 Python 3.11 或以上运行。这个小类模拟倍增规则,不代表 Python 内置列表的扩容实现。[None] * capacity 会在 Python 中初始化槽位,下面的计数只统计定义中的新元素写入与旧元素复制。若每次分配和初始化另计与新容量成正比的成本,追加总成本仍可用几何级数得到线性界,但常数不同。

python
class DynamicArray:
    def __init__(self):
        self.data: list[int | None] = [None]
        self.size = 0

    def potential(self):
        return 2 * self.size - len(self.data) + 1

    def append(self, value: int) -> int:
        copies = 0
        if self.size == len(self.data):
            grown = [None] * (2 * len(self.data))
            for index in range(self.size):
                grown[index] = self.data[index]
                copies += 1
            self.data = grown
        self.data[self.size] = value
        self.size += 1
        return copies + 1


array = DynamicArray()
costs = []
total = 0
for value in range(1, 9):
    before = array.potential()
    cost = array.append(value)
    costs.append(cost)
    total += cost
    assert cost + array.potential() - before == 3
    assert array.potential() >= 0
    assert total < 3 * array.size

print("actual costs:", costs)
print("first 5 total:", sum(costs[:5]))
print("first 8 total:", sum(costs))
print("final potential:", array.potential())
text
actual costs: [1, 2, 3, 1, 5, 1, 1, 1]
first 5 total: 12
first 8 total: 15
final potential: 9

策略变化要重新分析

固定容量增量会更频繁地复制元素。例如每次只加一槽,前 mm 次追加要复制 0+1+…+(m−1)0+1+…+(m-1) 个旧元素,成本为二次增长。若同时允许删除和缩容,扩容与缩容的触发阈值要留间隔。举例来说,满时加倍、使用率到四分之一再减半,可避免只插删一两个元素就反复扩缩。该场景需要另行证明。摊还常数并不消除单次复制导致的延迟尖峰。 MIT 摊还分析课程资料

本课练习

把执行次数改成 9,核对第 9 次的单次成本与总成本。再改成固定增加一槽,用单独的计数记录它的总复制量。下一章将从递归结构、调用栈和子问题规模入手建立递推式。

按自己的节奏,确认真正理解。

目录与阅读设置

阅读设置

17

记录一个想法

摊还分析入门

0 / 10000 · 笔记保存到账号。未提交的修改会在关闭、离开或刷新后丢失。

登录哪都通