数据结构与算法 / 系统课时
摊还分析入门
摊还分析入门
动态数组满时,某次追加可能要复制所有旧元素。摊还分析把连续操作作为一个整体,为任意合法前缀计算总成本。它不需要假设输入或操作是随机的。 MIT 摊还分析课程资料
学习目标
- 区分单次最坏成本、摊还成本和概率期望。
- 对倍增数组推导任意追加前缀的总成本。
- 用记账或势能核对扩容前后的预算。
先固定成本模型
从空数组和容量 1 开始,只执行追加。写入一个新元素计 1,复制一个旧元素也计 1。容量已满时先把容量加倍、复制旧元素,再写入新值。满数组已有 个元素时,这次追加的成本是 ,在这个状态下随 线性增长。接下来只计算写入和复制,不把具体语言的内存申请与初始化计入数值。 MIT 摊还分析课程资料

聚合法:对任意前缀求和
执行 次追加后,设最终容量为 。写入成本是 ,历次复制的规模依次是 ,合计 。当 时没有复制,同样有 。若发生最后一次扩容,旧容量 必小于已经追加的数量 ;若没有扩容,也满足 。所以总成本为 ,同时至少为 。每次追加的摊还复杂度为 。 MIT 摊还分析课程资料
不能对每个前缀都说复制次数小于 。前五次追加中发生了规模 1、2、4 的复制,共 7 次,总成本是 12。追加正好到 8 个时,总成本为 15。只观察容量正好用满的前缀会漏掉刚扩容的较高峰值。
记账与势能用同一个预算
记账时每次收取 3 单位,扣除实际成本后留下余额。可用势能给出这项余额的精确值。令当前元素数为 、容量为 ,取 。初始 ,势能为 0。之后扩容刚完成时 ,普通追加只使 增加,所以势能始终非负。
对一次操作,摊还费用等于实际成本加上势能变化。普通追加的实际成本为 1,势能增加 2,合计 3。若旧容量为 且已经装满,追加实际成本为 ,新容量 、新大小 ,势能变化为 ,合计仍为 3。累加后中间势能项抵消,已收费用 扣除当前势能就是实际总成本。 MIT 摊还分析课程资料
实跑扩容、计费与前缀
保存为 amortized_dynamic_array.py,用 Python 3.11 或以上运行。这个小类模拟倍增规则,不代表 Python 内置列表的扩容实现。[None] * capacity 会在 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())actual costs: [1, 2, 3, 1, 5, 1, 1, 1]
first 5 total: 12
first 8 total: 15
final potential: 9策略变化要重新分析
固定容量增量会更频繁地复制元素。例如每次只加一槽,前 次追加要复制 个旧元素,成本为二次增长。若同时允许删除和缩容,扩容与缩容的触发阈值要留间隔。举例来说,满时加倍、使用率到四分之一再减半,可避免只插删一两个元素就反复扩缩。该场景需要另行证明。摊还常数并不消除单次复制导致的延迟尖峰。 MIT 摊还分析课程资料
本课练习
把执行次数改成 9,核对第 9 次的单次成本与总成本。再改成固定增加一槽,用单独的计数记录它的总复制量。下一章将从递归结构、调用栈和子问题规模入手建立递推式。