摊还分析

许多数据结构的操作成本高度不均：绝大多数操作便宜，偶尔一次重组极贵。逐次最坏界仍是合法上界，却可能过松，因为每次最坏状态无法连续发生。例如扩容一次后数组留下大量空位，下一次昂贵扩容必须等待许多追加。摊还分析利用的正是操作之间的这种约束。

记账法让便宜操作预付信用，势能法把尚可支付的工作量写成当前状态的函数。两者都必须保证不能透支：否则任意昂贵操作都能靠任意负余额伪装成便宜操作。信用与势只是证明中的量，实现无须真的维护一笔钱。整个论证对每一个合法序列成立，包括对抗性序列，不需要假定哪些操作更可能出现。

考虑容量满时翻倍的动态数组理路动态数组Dynamic array · Resizable array以预留容量和偶发整体搬迁支持可变长度的连续序列结构。。从容量 $1$ 开始连续追加 $n$ 个元素，新元素本身共写入 $n$ 次，当 $n\ge 2$ 时，各次扩容搬迁的元素数恰为

例如追加到第 5 个元素时，搬迁发生在第 2、3、5 次追加，分别搬 1、2、4 个元素；加上五次新写入，总成本为 12。$n=1$ 时没有搬迁。因而任意这样的前缀总成本小于 $3n$，尽管某次追加可能单独搬迁 $\mathrm{\Theta }(n)$ 个元素，每次追加的摊还成本仍为 $O(1)$。这里把搬迁一个元素与写入一个新元素各计一个单位；若元素复制本身昂贵，还要乘上相应成本。

若扩容每次只增加固定的一个位置，第 $i$ 次追加就要搬迁 $i-1$ 个旧元素，总搬迁量成为 $0+1+\cdots +(n-1)=n(n-1)/2$。两种结构都偶尔重建，但只有几何扩容把下一次重建推迟足够久；“昂贵操作不常见”必须由具体更新规则支持。

二进制计数器的势能逐步变化 ​

从全零开始递增一个固定宽度的二进制计数器，以翻转一位计一个单位，取 $\mathrm{\Phi }$ 为当前 $1$ 的个数。若低位有 $t$ 个连续的 $1$，且尚未溢出，一次递增将它们改成 $0$，再把前面的一个 $0$ 改成 $1$。实际成本为 $t+1$，势能变化为 $1-t$，摊还成本恰为 $2$。

例如 0111 → 1000 实际翻转四位，势从 $3$ 降到 $1$，故摊还成本为 $4+(1-3)=2$。四次翻转没有消失，而是由先前累积的两个单位信用承担。全零初态势为零、终态势非负，因此任意前 $N$ 次递增总翻转数至多 $2N$。若采用模计数，全为 $1$ 时翻成全零的摊还成本为零，仍满足上界；若要求任意精度表示，则应另外计入存储增长成本。

带 multipop 的栈理路栈Stack · LIFO stack以栈顶为唯一更新端、按后进先出规则组织元素的抽象数据类型；接口语义与具体表示的成本分别规定。也可按同一原则计费：每个元素入栈时预付它唯一一次出栈的费用。关键不是某次能弹出多少元素，而是同一个已入栈元素不能在这条操作历史里被弹出两次。

边界在于摊还界的“总量”性质。摊还 $O(1)$ 不承诺任何单次操作快——动态数组的某次追加就是 $\mathrm{\Theta }(n)$；它也不是概率语句，不提供尾界。需要逐操作延迟时，去摊还化理路去摊还化Deamortization把批量工作拆成有截止期的微步，以顺序动态数组的读、写、追加证明权威槽不变量、迁移期限和逐操作最坏界。会把一次大工作拆到后续操作，但还必须证明后台预算追得上新增工作。若允许的初态使势能欠账没有统一下界，常数 $K$ 就不存在。持久化结构理路持久化数据结构Persistent data structure · Persistence in data structures更新产生新版本而保留旧版本可访问性，并通过结构共享控制时间与空间的数据结构技术。还能从同一旧版本多次分叉，单线版本链上存下的“信用”可能被重复使用，原摊还证明必须重新审计。

摊还分析是许多经典结论的语言：动态数组的常数追加、并查集理路并查集Disjoint-set union · Union-find维护不交集合划分并支持合并与代表元查询的数据结构。近乎常数的合并与查询、伸展树的对数摊还访问界、Fibonacci 堆各类操作的摊还界，以及垃圾回收、扫描线里“每个元素至多进出一次”式的论证。全局重建理路全局重建Global rebuilding在坏度量越界时从活动元素重建结构，并把线性成本收费给足够多次更新。把昂贵重构记到账上，自调整结构理路自调整数据结构Self-adjusting data structure根据访问历史重排内部表示的数据结构设计；具体序列敏感界还需逐种结构证明。让访问序列决定结构形状，并查集摊还界理路并查集的逆 Ackermann 摊还界union-find inverse Ackermann bound · DSU amortized bound按秩合并配合路径压缩时，并查集操作序列具有逆 Ackermann 摊还复杂度。则展示多种启发式怎样共同产生反 Ackermann 总界；这些页面各自证明具体账本，本页不替它们展开。最具一般性的势能法见势能法理路势能法Potential method用数据结构状态势函数的增量调整单步记账，以控制操作序列的总成本。条目，选择势函数的本质，是为“未来必然发生的工作”找到一个可守恒的量。

配套实验 ​

字典与迁移的成本账本把一条历史的实际费用、对所有历史的维护摊还界、随机查找期望和单次最坏成本分开。可以先复算数值，再指出每一项推广需要哪条额外假设。