14.3 补充：摊还分析

前置：渐进分析。本页用容量翻倍的动态数组说明聚合、记账与势能三种方法，再用二进制计数器区分摊还界与平均情况。

一次 append 为什么可能很慢

动态数组还有空槽时，追加只写一个位置。数组已满时，则要分配更大的存储、复制全部旧元素，再写入新值。单次最坏成本是 Θ(n)，但从空数组开始连续 n 次追加的总成本仍为 Θ(n)。

摊还分析对一串操作给出每次操作的保证，不假设输入服从某种概率分布。它也不声称每次都快；需要严格尾延迟的系统仍要考虑扩容停顿，或采用预留容量、分段存储与增量迁移。

先记录真实成本

下面把一次普通写入记为 1，把扩容时复制每个旧元素也各记为 1。这是分析用的成本计数器，未计入 Python 创建 [None] 数组、释放旧列表及记录轨迹的成本，并非耗时测量。把这些线性初始化成本计入，几何扩容的总渐进界仍不变，具体常数会变。

class DynamicArray:
    def __init__(self):
        self._data = [None]
        self._size = 0
        self._actual_costs = []

    def append(self, value):
        actual = 1
        if self._size == len(self._data):
            old = self._data
            self._data = [None] * (2 * len(old))
            for index, item in enumerate(old):
                self._data[index] = item
                actual += 1

        self._data[self._size] = value
        self._size += 1
        self._actual_costs.append(actual)

    @property
    def capacity(self):
        return len(self._data)

    def to_list(self):
        return self._data[:self._size]

    def actual_costs(self):
        return self._actual_costs.copy()

array = DynamicArray()
for number in range(16):
    array.append(number)

assert array.to_list() == list(range(16))
assert array.capacity == 16
assert array.actual_costs() == [1, 2, 3, 1, 5, 1, 1, 1, 9, 1, 1, 1, 1, 1, 1, 1]
assert sum(array.actual_costs()) == 31

扩容成本出现在第 2、3、5、9 次追加，因为旧容量依次是 1、2、4、8。昂贵步骤仍然存在，只是间隔按几何速度拉长。

聚合分析：先算总账

n 次写入本身成本为 n。容量翻倍时，复制量形成：

copies = 1 + 2 + ... + C/2 = C - 1 < 2n
actual total = n + C - 1 < 3n  (n > 0, C = final capacity)

n>0 时，最后容量 C 满足 n <= C < 2n，所以任意前缀的总成本小于 3n，每次追加摊还 O(1)。只有 n 恰为二次幂时，才有 C=n、总成本 2n-1。例如 n=9，复制 15 次、写入 9 次，总成本 24，已经超过 2n。这个上界不需要“随机追加”假设。

若把“容量乘以 2”改为“容量加 1”，复制量会变成 1+2+...+(n-1)，总成本 Θ(n²)。几何扩容是结论成立的关键前提。

记账法：便宜操作为未来存信用

设每次追加收取 3 个单位：

• 1 个支付当前写入；
• 剩余信用保留，用于以后复制旧元素。

下面直接检查任何操作前缀的信用都不为负。

def accounting_costs(operation_count):
    if not isinstance(operation_count, int) or operation_count < 0:
        raise ValueError("operation_count must be a non-negative integer")
    capacity = 1
    size = 0
    credit = 0
    trace = []

    for _ in range(operation_count):
        actual = 1
        if size == capacity:
            actual += capacity
            capacity *= 2
        size += 1
        credit += 3 - actual
        if credit < 0:
            raise AssertionError("credit became negative")
        trace.append((actual, credit))

    return trace

trace = accounting_costs(1_000)
assert all(actual <= 3 + previous_credit
           for (actual, _), previous_credit
           in zip(trace, [0] + [credit for _, credit in trace[:-1]]))

收取 3 不是唯一方案，只要能证明信用不会透支即可。信用是分析工具，不是程序真的要维护的字段。Cornell 的摊还分析课程也用动态数组比较这些分析方法。

势能法：把信用写成状态函数

势能可定义为：

Phi = 0                         size = 0
Phi = 2 * size - capacity       size > 0

容量翻倍且不缩容时，非空数组始终满足 capacity/2 < size <= capacity，所以势能非负。摊还成本定义为：

amortized = actual + Phi_after - Phi_before

def potential_costs(operation_count):
    if not isinstance(operation_count, int) or operation_count < 0:
        raise ValueError("operation_count must be a non-negative integer")
    capacity = 1
    size = 0
    potential = 0
    amortized_costs = []

    for _ in range(operation_count):
        before = potential
        actual = 1
        if size == capacity:
            actual += capacity
            capacity *= 2
        size += 1
        potential = 2 * size - capacity
        amortized_costs.append(actual + potential - before)

    return amortized_costs

costs = potential_costs(1_000)
assert costs[0] == 2
assert all(cost <= 3 for cost in costs)

第一次追加的摊还成本是 2，之后不超过 3。若对空数组也直接使用 2*size-capacity，初始势能会是 -1，与这里设定的 0 不同；混用两套初值会把第一步算错。势能必须在所有状态上定义一致。

把摊还成本求和时，中间势能会相消：

sum(amortized) = sum(actual) + Phi_final - Phi_initial

因为初末势能都非负且初始为 0，实际总成本不会超过摊还总成本。

二进制计数器：一位可能反复翻转

从 0 开始递增。某次操作可能把末尾一长串 1 清零，再把前一位 0 改成 1，单次最坏 Θ(log n)。但最低位每次翻转，下一位每两次翻转，更高位频率继续减半。

def count_bit_flips(increments):
    if not isinstance(increments, int) or increments < 0:
        raise ValueError("increments must be a non-negative integer")

    value = 0
    total = 0
    for _ in range(increments):
        probe = value
        flips = 1
        while probe & 1:
            flips += 1
            probe >>= 1
        total += flips
        value += 1
    return total

for n in (1, 2, 4, 8, 16, 64):
    assert count_bit_flips(n) == 2 * n - 1

对于 n>0，前 n 次递增的总翻转次数为 n + floor(n/2) + floor(n/4) + ... = 2n - popcount(n) < 2n，其中 popcount(n) 是 n 的二进制 1 的个数。示例选的二次幂恰有一个 1，因此都是 2n-1；n=0 时总数为 0。按一次位翻转为单位，摊还成本为 O(1)。这个 Python 函数用整数移位模拟计数，没有声称任意大整数移位和加法都只花常数时间。这仍是确定性的操作序列结论，不是对随机计数值取平均。

三种方法怎样选

方法	适合的入口	要证明什么
聚合	总成本能直接求和	任意 n 次操作总成本上界
记账	能直观说明谁为谁存信用	所有前缀信用不为负
势能	多种操作共享复杂状态	势能定义一致、非负，摊还和能覆盖实际和

并查集的反 Ackermann 界、伸展树的对数摊还界需要更精细的势能函数。本页的动态数组证明不能直接搬过去；每种数据结构都要根据状态变化选分析量。

动手算一串操作

1. 手算前 9 次动态数组追加的实际成本、信用和势能。
2. 把增长因子改为 1.5，讨论取整后如何保持几何级数上界。
3. 动态数组若在利用率低时缩容，怎样避免容量在边界附近来回抖动？
4. 栈支持 push 与 multipop(k)，从空栈开始，用“栈中元素数”作势能证明连续 n 次操作总成本 O(n)；若初始已有 s 个元素，上界应怎样变化？
5. 解释为什么“摊还 O(1)”不能作为单次延迟 SLA。

算完整本账

摊还分析没有抹掉扩容复制。它把整串操作的真实成本加总，再证明昂贵步骤出现得足够少。聚合、记账和势能只是三种记账方式；前提、状态函数和操作序列必须写清。

继续阅读：高级数据结构，其中并查集的路径压缩就是另一个“单次看不清、整串才有界”的例子。