摊还分析

许多数据结构的操作成本高度不均：绝大多数操作便宜，偶尔一次重组极贵。逐次按最坏情形计费，会把整段序列的估计抬到不真实的量级；摊还分析的观点是让便宜操作“预存”一点成本——记账法里是显式的信用，势能法里是状态中蓄积的势——昂贵操作发生时恰好由存款支付。势能的物理类比颇为贴切：结构越“紧绷”（如数组越接近装满），势越高，重组释放势能；但类比在一处失效——信用与势纯属分析中的记账，数据结构里并不真的存着这笔钱，运行时也无须任何额外维护。它与平均情形分析的区别是根本性的：摊还界对每一个操作序列都成立，包括对抗性构造的序列。

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

因此任意这样的前缀总成本小于 $3n$，尽管某次追加可能单独搬迁 $\mathrm{\Theta }(n)$ 个元素，每次追加的摊还成本仍为 $O(1)$。二进制计数器可取 $\mathrm{\Phi }$ 为 $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用数据结构状态势能的变化修正实际成本以界定均摊成本。条目，选择势函数的本质，是为“未来必然发生的工作”找到一个可守恒的量。