OI-wiki 均摊复杂度完全指南聚合分析、记账法与势能分析详解【免费下载链接】OI-wiki:star2: Wiki of OI / ICPC for everyone. 某大型游戏线上攻略内含炫酷算术魔法项目地址: https://gitcode.com/GitHub_Trending/oi/OI-wiki本文是 OI-wiki 基础算法章节中「均摊复杂度」主题的技术指南系统讲解均摊分析Amortized Analysis的三种经典方法——聚合分析、记账分析与势能分析并以 Cvector动态数组扩容和堆栈操作为核心算例逐步推导同时结合 OI-wiki 仓库中并查集、Splay、替罪羊树等数据结构的复杂度证明展示均摊分析在算法竞赛中的实际应用。读完本文你将掌握如何为一个单次可能很慢、整体却不慢的数据结构操作序列建立严格的时间复杂度上界。前置知识时间复杂度回顾均摊复杂度是时间复杂度分析的延伸。在 docs/basic/complexity.md 中已经建立了两条关键认知渐近符号大 $O$ 符号描述函数的渐近上界——$f(n)O(g(n))$ 当且仅当 $\exists c,n_00$使得 $\forall n \ge n_0$$0\le f(n)\le c\cdot g(n)$。复杂度分析通常关注上界因为竞赛中要保证算法能通过数据范围内的任何输入。最坏时间复杂度竞赛中一般考虑每个输入规模下用时最长的输入对应的复杂度。但最坏时间复杂度的粒度往往太粗一个数据结构可能偶尔执行一次 $O(n)$ 的重建操作其余 $n-1$ 次操作都是 $O(1)$若单看最坏情况每次操作都被记为 $O(n)$这显然低估了该数据结构的实际表现。均摊分析正是为了解决这一问题而生的工具。均摊分析核心思想与适用边界均摊分析Amortized Analysis是一种用于分析算法和动态数据结构性能的技术。它不聚焦于单次操作的成本而是通过评估一系列操作的平均成本为整体性能提供更准确的评估。它有两条重要边界不涉及概率均摊分析与概率无关它不是平均情况分析保证最坏情况它确保的是最坏情况下每次操作的平均时间而非系统的平均性能。在最坏情况下均摊分析通过把高成本操作的开销分摊到低成本操作上确保整体操作的平均成本保持在合理范围内。一个直觉类比是日常生活中水电费按月缴纳但高峰期使用量大均摊分析相当于将高峰期的大额开销平摊到每一笔小额日常使用中从而得到一个稳定的月均成本。均摊分析通常采用三种主要方法聚合分析Aggregate Analysis、记账分析Accounting Method和势能分析Potential Method。它们各有侧重适用于不同场景但共同目标是通过均衡操作成本优化数据结构在最坏情况下的整体性能表现。引入动态数组的扩容问题考虑一个可扩展的数组例如 C 中的vector其初始容量为 $m1$。每次插入新元素时如果数组已满则需要将数组的大小加倍然后将原数组中的元素复制到新数组中最后插入新元素。这个场景具有鲜明的不均摊则失真特征扩容的那一次操作要复制 $O(m)$ 个元素而其余插入都只要 $O(1)$。接下来就以动态数组插入操作为主线用三种方法分别分析其均摊成本你会发现三种方法殊途同归都得到 $O(1)$ 的结论。聚合分析聚合分析Aggregate Analysis通过计算一系列操作的总成本再将其平均到每次操作上从而得出每次操作的均摊时间复杂度。它是三种方法中最直观的一种。动态数组的两个关键成本以动态数组为例插入操作有两个关键成本如果数组未满插入操作的成本为 $O(1)$如果数组已满插入操作需要扩容扩容后复制元素的成本为 $O(m)$其中 $m$ 为当前数组的大小。n 次插入的总成本计算 $n$ 次插入操作的总成本可以拆成两部分插入操作的成本每次插入新元素的直接成本是常数时间 $O(1)$对于 $n$ 次操作总成本是 $O(n)$。数组扩容的成本每次扩容涉及复制原数组元素到新数组。这些操作发生在数组大小为 $1,2,4,\dots,2^k$ 的时刻其中 $2^k$ 是小于等于 $n$ 的最大幂。扩容操作的成本分别是 $1,2,4,\dots,2^{k-1}$总和为$$ 1 2 4 \cdots 2^{k-1} 2^k - 1 $$这是一个等比数列求和结果为 $O(n)$。因此该数组总的插入成本为 $O(n)$均摊到每次操作的成本为 $O(1)$。即使在最坏情况下平均每次插入操作的成本依然是常数时间——这正是聚合分析的力量它不回避最坏情况而是把最坏情况摊进整个操作序列中。记账分析记账法Accounting Method通过为每次操作预先分配一个固定的均摊成本来确保所有操作的总成本不超过这些预分配成本的总和。记账法类似于一种费用前置支付机制较低成本的操作会存储一部分费用用于支付未来高成本的操作。动态数组的记账方案以动态数组为例可以为每次插入分配固定的均摊成本确保需要扩容时已经预留了足够的费用。1. 费用分配假设每次插入操作的实际成本为 $1$均摊成本设为 $3$其中 $1$ 用于当前插入操作$2$ 用于未来可能的扩容操作。2. 费用使用当数组已满时需要进行扩容操作实际成本为 $O(m)$其中 $m$ 是当前数组的大小假设扩容前数组的元素数量为 $n$由于原数组的后半部分 $n/2$ 个元素在插入时共预存了 $n$ 单位的均摊成本恰好足够支付扩容操作的成本。具体示例推演下面用一段直观的推演展示记账法的运作过程初始状态 arr [1, 2, 3, 4] // 初始数组 amount [2, 2, 2, 2] // 每个元素预存的费用 // 第一轮扩容数组已满需要扩容 arr [1, 2, 3, 4, null, null, null, null] // 扩容后数组 amount [2, 2, 0, 0, 0, 0, 0, 0] // 3, 4 的费用用于支付扩容 // 继续插入新元素直至再次满载 arr [1, 2, 3, 4, 5, 6, 7, 8] // 继续填充数组 amount [2, 2, 0, 0, 2, 2, 2, 2] // 新插入的元素同样预存费用 // 第二轮扩容数组再次满载需要更大的空间 arr [1, 2, 3, 4, 5, 6, 7, 8, null, null, null, null, null, null, null, null] // 扩容后数组 amount [2, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0] // 5, 6, 7, 8 的费用用于支付扩容注意这里的记账细节每个新插入的元素预存 $2$ 单位费用均摊成本 $3$ 减去实际成本 $1$。扩容发生时原数组中后一半元素——它们是最近才插入的、预存费用尚未被使用的元素——贡献出预存费用来支付整体复制成本。这保证了费用账户永不为负从而每次操作的均摊成本维持在 $O(1)$。记账法的核心约束是预存费用的总余额必须始终非负即任何前缀操作序列中均摊成本之和不小于实际成本之和。只要满足这一点均摊成本的上界就是成立的。势能分析势能分析Potential Method是三种方法中最强大、也最常用于竞赛数据结构复杂度证明的方法。它通过定义一个势能函数通常表示为 $\Phi$来度量数据结构的潜在能量——即系统状态中的预留资源这些资源可以用来支付未来的高成本操作。原理与数学框架首先定义状态$S$ 为某一时刻数据结构的状态该状态可能包含元素数量、容量、指针等信息。定义初始状态为 $S_0$即未进行任何操作时的状态。其次定义势能函数 $\Phi(S)$它度量数据结构状态 $S$ 的势能须满足两个性质初始势能在初始状态 $S_0$ 下$\Phi(S_0)0$非负性在任意状态 $S$ 下$\Phi(S) \geq 0$。对于每个操作其均摊成本 $\hat{c}$ 定义为$$ \hat{c} c \Phi(S) - \Phi(S) $$其中 $c$ 为操作的实际成本$S$ 和 $S$ 分别表示操作前后的数据结构状态。该公式表明均摊成本等于实际成本加上势能的变化。如果操作增加了势能$\Phi(S) \Phi(S)$则均摊成本上升如果操作消耗了势能$\Phi(S) \Phi(S)$则均摊成本下降。设 $S_1, S_2, \dots, S_m$ 为从初始状态 $S_0$ 开始、经过 $m$ 次操作后产生的状态序列$c_i$ 为第 $i$ 次操作的实际开销则第 $i$ 次操作的均摊成本 $p_i$ 为$$ p_i c_i \Phi(S_i) - \Phi(S_{i-1}) $$因此$m$ 次操作的总时间花销为$$ \sum_{i1}^m c_i \sum_{i1}^m p_i \Phi(S_0) - \Phi(S_m) $$由于 $\Phi(S) \geq \Phi(S_0)$总时间花销的上界为$$ \sum_{i1}^m p_i \geq \sum_{i1}^m c_i $$因此若 $p_i O(T(n))$则 $O(T(n))$ 是均摊复杂度的一个上界。这就是势能分析能给出严格复杂度上界的核心逻辑势能的存储与释放恰好将高成本操作的尖峰抹平。示例动态数组的扩容分析以动态数组vector的插入操作为例定义势能函数$$ \Phi(h) 2n - m $$其中 $n$ 是数组中的元素数量$m$ 是数组的当前容量。这个势能函数反映了数组中剩余可用空间的数量即当前容量与实际使用空间之间的差异。情况一插入操作无需扩容操作成本$O(1)$因为只需插入一个元素。势能变化插入后元素数量增加 $1$势能增加 $2$$$ \Phi(h) - \Phi(h) 2(n1) - m - (2n - m) 2 $$均摊成本$1 2 3$。情况二插入操作触发扩容假设当前容量 $m n$插入一个新元素时触发扩容新容量变为 $2n$。操作成本$O(n)$因为需要将所有元素复制到新数组中并插入新元素。势能变化扩容后容量增加势能减少变化大小为 $2 - n$$$ \Phi(h) - \Phi(h) 2(n1) - 2n - (2n - n) 2 - n $$均摊成本$n 1 (2 - n) 3$。两种情况的均摊成本都是 $3$即 $O(1)$。尽管扩容操作的实际成本高达 $O(n)$但由于势能函数的设计扩容前的满数组积累了 $2n - n n$ 单位的势能恰好抵消复制成本整体均摊成本仍然保持在常数级别。这里也能看出势能分析与记账分析的对应关系势能函数 $\Phi(h) 2n - m$ 中的系数 $2$正是记账法中每次插入预存 $2$ 单位费用的数学化表达。扩展示例堆栈操作的三方法对比堆栈操作是均摊分析的经典应用场景。假设堆栈 $S$ 支持以下三种操作操作说明实际成本 $c_i$S.push(x)将元素 x 入栈$1$S.pop()弹出栈顶元素$1$S.multi-pop(k)弹出栈顶 k 个元素$O(\min(\lvert S\rvert, k))$下面用三种方法分别分析体会它们在同一个问题上各显神通。聚合分析法聚合分析将计算所有操作的总成本并平均分摊到每个操作上。对于 $n_{push}$ 次push(x)每次成本 $O(1)$总成本 $O(n_{push})$对于 $n_{pop}$ 次pop()每次成本 $O(1)$总成本 $O(n_{pop})$对于 $n_{multi-pop}$ 次multi-pop(k)尽管单次实际成本为 $O(\min(\lvert S\rvert, k))$但这些操作弹出的元素数量不会超过之前push(x)的元素数量因此总成本仍受 $n_{push}$ 的约束。由于总操作次数 $n n_{push} n_{pop} n_{multi-pop} \leq 2 \times n_{push}$总成本为 $O(n_{push}) O(n)$每次操作的均摊成本为 $O(n)/n O(1)$。记账分析法记账分析为每次push(x)预留一部分费用以支付未来可能的pop()或multi-pop(k)。S.push(x)假设均摊成本为 $2$其中 $1$ 单位用于当前操作另 $1$ 单位存储为费用用于支付未来的pop()或multi-pop(k)S.pop()实际成本为 $1$但之前的push(x)已为其预存了 $1$ 单位费用因此均摊成本为 $0$S.multi-pop(k)每个弹出的元素的实际成本为 $1$可以由该元素push(x)时预存的费用支付因此均摊成本为 $0$。入栈操作预存的费用足以支付未来该元素的出栈操作因此每次操作的均摊成本为 $O(1)$。注意这里比动态数组的例子更精确费用是绑定到具体元素上的每个元素入栈预存 $1$ 单位恰好覆盖它未来被弹出的 $1$ 单位成本账户严格收支平衡。势能分析法势能分析定义势能函数来衡量堆栈状态并利用势能变化平衡操作成本。势能函数设 $\Phi(h)$ 为堆栈中的元素数量即 $\Phi(h)\lvert S\rvert$每个元素贡献 $1$ 单位势能S.push(x)元素数量增加 $1$势能增加 $1$均摊成本为 $112$S.pop()元素数量减少 $1$势能减少 $1$均摊成本为 $1-10$S.multi-pop(k)弹出 $k$ 个元素势能减少 $k$均摊成本为 $k-k0$。通过以上势能函数设计push(x)的均摊成本为 $2$pop()和multi-pop(k)的均摊成本为 $0$。因此所有堆栈操作的均摊成本均为 $O(1)$。三种方法的异同与选用方法核心手段动态数组均摊成本堆栈均摊成本适用特点聚合分析计算总成本再除以操作数$O(1)$$O(1)$最直观但需要先能算出整个序列的总成本记账分析为操作预存费用余额非负$O(1)$$O(1)$直观体现前置支付适合逐操作解释势能分析定义势能函数 $\Phi$用 $\hat{c}c\Delta\Phi$ 记账$O(1)$$O(1)$最通用、最强大适合复杂的局部操作分析三者对同一问题的结论完全一致动态数组与堆栈的均摊成本均为 $O(1)$这正是它们内在等价性的体现。实际使用中聚合分析适合整体趋势明显的序列记账分析适合逐操作解释费用流向的教学场景而势能分析因为可以对每个操作独立定义 $\hat{c}$不必关心操作之间的顺序细节在证明复杂数据结构的均摊界时最为常用。仓库中的实战案例均摊分析在 OI-wiki 数据结构中的应用均摊分析不是孤立的理论OI-wiki 的数据结构章节中多处直接运用了本文介绍的方法尤其是势能分析来证明复杂度上界。以下案例可以作为延伸阅读印证方法的实战价值并查集路径压缩 按秩合并docs/ds/dsu-complexity.md 是势能分析最硬核的应用。它定义了基于 $\alpha(n)$反阿克曼函数、秩 $\mathit{rnk}(x)$、层级 $\mathit{level}(x)$ 与迭代数 $\mathit{iter}(x)$ 的势能函数通过证明union操作中唯一可能增加势能的点是 $y$最多增加 $\alpha(n)$以及find操作中至少有 $s-\alpha(n)$ 个节点的势能至少减少 $1$最终得出并查集均摊时间复杂度为 $\Theta(\alpha(n))$ 的结论——这正是每次查询几乎常数这一直观印象的严格证明。Splay 树docs/ds/splay.md 用势能分析法推导伸展操作的均摊复杂度。它定义 $w(x)\sum_{y\in subtree(x)} s(y)$ 形式的权重函数逐一分析zig、zig-zig、zig-zag三种旋转操作的均摊成本分别不超过 $3(w(x)-w(x))$ 与 $3(w(x)-w(x))1$证明单次伸展操作均摊复杂度为 $O(\log n)$从而插入、查询、删除均为均摊 $O(\log N)$。替罪羊树docs/ds/sgt.md 利用均摊分析解释为什么偶发重构不拖累整体通过摊还分析可知若每次插入时在自根到节点的路径上每个节点增加 $\Theta(1)$ 势能那么到节点 $x$ 发生子树重构时已在该节点累积了 $\Omega(\lvert T_x\rvert)$ 的势能足以偿还重构成本 $\Theta(\lvert T_x\rvert)$从而 $\Theta(n)$ 次插入的均摊复杂度为 $O(\log n)$。配对堆docs/ds/pairing-heap.md 明确指出配对堆的复杂度基于势能分析的均摊复杂度且正是因为这一点无法可持久化——这从反面印证了均摊分析与最坏情况保证如可持久化所需的单次 $O(\log n)$ 保证之间的区别与本文开篇均摊分析只能确保最坏情况性能的每次操作耗费的平均时间的边界描述遥相呼应。斜堆docs/ds/leftist-tree.md 中斜堆作为左偏树的自适应形式合并时无条件交换路径上的节点根据均摊分析其插入、合并、删除最小值复杂度为 $O(\log n)$。双栈模拟队列docs/ds/queue.md 是均摊分析在基础数据结构中的典型应用——每个元素只会进入/转移/弹出一次均摊复杂度 $O(1)$。该文还讨论了均摊分析的失效边界当某个栈为空时交替查询队首队尾会导致均摊分析失效需要调整转移策略来维持均摊常数时间这对理解均摊分析的适用前提极具价值。LCTLink-Cut Treedocs/ds/lct.md 中Access操作的时间复杂度证明同样依赖势能分析定义势能函数 $\Phi$ 为所有重虚边的数量均摊成本 $c_i t_i \Delta \Phi_i$最终得到Access及Cut、Link、Findroot等操作均摊 $O(\log n)$ 的结论。从这些案例可以总结出一条规律凡是平时攒、关键时花的数据结构都天然适合用均摊分析来刻画——势能函数的设计目标就是让攒与花恰好互相抵消从而把复杂度的尖峰压平为常数。参考资料均摊分析概念与三种方法的原始出处可参见维基百科 Amortized analysis 词条与 Cornell CS 3110 课程 Lecture 20: Amortized Analysis原文档 docs/basic/amortized-analysis.md 末尾所列。本文涉及的前置复杂度概念详见 docs/basic/complexity.md相关数据结构复杂度证明的仓库内延伸阅读路径已在上文逐一给出。【免费下载链接】OI-wiki:star2: Wiki of OI / ICPC for everyone. 某大型游戏线上攻略内含炫酷算术魔法项目地址: https://gitcode.com/GitHub_Trending/oi/OI-wiki创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考 OI-wiki 均摊复杂度完全指南：聚合分析、记账法与势能分析详解
OI-wiki 均摊复杂度完全指南聚合分析、记账法与势能分析详解【免费下载链接】OI-wiki:star2: Wiki of OI / ICPC for everyone. 某大型游戏线上攻略内含炫酷算术魔法项目地址: https://gitcode.com/GitHub_Trending/oi/OI-wiki本文是 OI-wiki 基础算法章节中「均摊复杂度」主题的技术指南系统讲解均摊分析Amortized Analysis的三种经典方法——聚合分析、记账分析与势能分析并以 Cvector动态数组扩容和堆栈操作为核心算例逐步推导同时结合 OI-wiki 仓库中并查集、Splay、替罪羊树等数据结构的复杂度证明展示均摊分析在算法竞赛中的实际应用。读完本文你将掌握如何为一个单次可能很慢、整体却不慢的数据结构操作序列建立严格的时间复杂度上界。前置知识时间复杂度回顾均摊复杂度是时间复杂度分析的延伸。在 docs/basic/complexity.md 中已经建立了两条关键认知渐近符号大 $O$ 符号描述函数的渐近上界——$f(n)O(g(n))$ 当且仅当 $\exists c,n_00$使得 $\forall n \ge n_0$$0\le f(n)\le c\cdot g(n)$。复杂度分析通常关注上界因为竞赛中要保证算法能通过数据范围内的任何输入。最坏时间复杂度竞赛中一般考虑每个输入规模下用时最长的输入对应的复杂度。但最坏时间复杂度的粒度往往太粗一个数据结构可能偶尔执行一次 $O(n)$ 的重建操作其余 $n-1$ 次操作都是 $O(1)$若单看最坏情况每次操作都被记为 $O(n)$这显然低估了该数据结构的实际表现。均摊分析正是为了解决这一问题而生的工具。均摊分析核心思想与适用边界均摊分析Amortized Analysis是一种用于分析算法和动态数据结构性能的技术。它不聚焦于单次操作的成本而是通过评估一系列操作的平均成本为整体性能提供更准确的评估。它有两条重要边界不涉及概率均摊分析与概率无关它不是平均情况分析保证最坏情况它确保的是最坏情况下每次操作的平均时间而非系统的平均性能。在最坏情况下均摊分析通过把高成本操作的开销分摊到低成本操作上确保整体操作的平均成本保持在合理范围内。一个直觉类比是日常生活中水电费按月缴纳但高峰期使用量大均摊分析相当于将高峰期的大额开销平摊到每一笔小额日常使用中从而得到一个稳定的月均成本。均摊分析通常采用三种主要方法聚合分析Aggregate Analysis、记账分析Accounting Method和势能分析Potential Method。它们各有侧重适用于不同场景但共同目标是通过均衡操作成本优化数据结构在最坏情况下的整体性能表现。引入动态数组的扩容问题考虑一个可扩展的数组例如 C 中的vector其初始容量为 $m1$。每次插入新元素时如果数组已满则需要将数组的大小加倍然后将原数组中的元素复制到新数组中最后插入新元素。这个场景具有鲜明的不均摊则失真特征扩容的那一次操作要复制 $O(m)$ 个元素而其余插入都只要 $O(1)$。接下来就以动态数组插入操作为主线用三种方法分别分析其均摊成本你会发现三种方法殊途同归都得到 $O(1)$ 的结论。聚合分析聚合分析Aggregate Analysis通过计算一系列操作的总成本再将其平均到每次操作上从而得出每次操作的均摊时间复杂度。它是三种方法中最直观的一种。动态数组的两个关键成本以动态数组为例插入操作有两个关键成本如果数组未满插入操作的成本为 $O(1)$如果数组已满插入操作需要扩容扩容后复制元素的成本为 $O(m)$其中 $m$ 为当前数组的大小。n 次插入的总成本计算 $n$ 次插入操作的总成本可以拆成两部分插入操作的成本每次插入新元素的直接成本是常数时间 $O(1)$对于 $n$ 次操作总成本是 $O(n)$。数组扩容的成本每次扩容涉及复制原数组元素到新数组。这些操作发生在数组大小为 $1,2,4,\dots,2^k$ 的时刻其中 $2^k$ 是小于等于 $n$ 的最大幂。扩容操作的成本分别是 $1,2,4,\dots,2^{k-1}$总和为$$ 1 2 4 \cdots 2^{k-1} 2^k - 1 $$这是一个等比数列求和结果为 $O(n)$。因此该数组总的插入成本为 $O(n)$均摊到每次操作的成本为 $O(1)$。即使在最坏情况下平均每次插入操作的成本依然是常数时间——这正是聚合分析的力量它不回避最坏情况而是把最坏情况摊进整个操作序列中。记账分析记账法Accounting Method通过为每次操作预先分配一个固定的均摊成本来确保所有操作的总成本不超过这些预分配成本的总和。记账法类似于一种费用前置支付机制较低成本的操作会存储一部分费用用于支付未来高成本的操作。动态数组的记账方案以动态数组为例可以为每次插入分配固定的均摊成本确保需要扩容时已经预留了足够的费用。1. 费用分配假设每次插入操作的实际成本为 $1$均摊成本设为 $3$其中 $1$ 用于当前插入操作$2$ 用于未来可能的扩容操作。2. 费用使用当数组已满时需要进行扩容操作实际成本为 $O(m)$其中 $m$ 是当前数组的大小假设扩容前数组的元素数量为 $n$由于原数组的后半部分 $n/2$ 个元素在插入时共预存了 $n$ 单位的均摊成本恰好足够支付扩容操作的成本。具体示例推演下面用一段直观的推演展示记账法的运作过程初始状态 arr [1, 2, 3, 4] // 初始数组 amount [2, 2, 2, 2] // 每个元素预存的费用 // 第一轮扩容数组已满需要扩容 arr [1, 2, 3, 4, null, null, null, null] // 扩容后数组 amount [2, 2, 0, 0, 0, 0, 0, 0] // 3, 4 的费用用于支付扩容 // 继续插入新元素直至再次满载 arr [1, 2, 3, 4, 5, 6, 7, 8] // 继续填充数组 amount [2, 2, 0, 0, 2, 2, 2, 2] // 新插入的元素同样预存费用 // 第二轮扩容数组再次满载需要更大的空间 arr [1, 2, 3, 4, 5, 6, 7, 8, null, null, null, null, null, null, null, null] // 扩容后数组 amount [2, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0] // 5, 6, 7, 8 的费用用于支付扩容注意这里的记账细节每个新插入的元素预存 $2$ 单位费用均摊成本 $3$ 减去实际成本 $1$。扩容发生时原数组中后一半元素——它们是最近才插入的、预存费用尚未被使用的元素——贡献出预存费用来支付整体复制成本。这保证了费用账户永不为负从而每次操作的均摊成本维持在 $O(1)$。记账法的核心约束是预存费用的总余额必须始终非负即任何前缀操作序列中均摊成本之和不小于实际成本之和。只要满足这一点均摊成本的上界就是成立的。势能分析势能分析Potential Method是三种方法中最强大、也最常用于竞赛数据结构复杂度证明的方法。它通过定义一个势能函数通常表示为 $\Phi$来度量数据结构的潜在能量——即系统状态中的预留资源这些资源可以用来支付未来的高成本操作。原理与数学框架首先定义状态$S$ 为某一时刻数据结构的状态该状态可能包含元素数量、容量、指针等信息。定义初始状态为 $S_0$即未进行任何操作时的状态。其次定义势能函数 $\Phi(S)$它度量数据结构状态 $S$ 的势能须满足两个性质初始势能在初始状态 $S_0$ 下$\Phi(S_0)0$非负性在任意状态 $S$ 下$\Phi(S) \geq 0$。对于每个操作其均摊成本 $\hat{c}$ 定义为$$ \hat{c} c \Phi(S) - \Phi(S) $$其中 $c$ 为操作的实际成本$S$ 和 $S$ 分别表示操作前后的数据结构状态。该公式表明均摊成本等于实际成本加上势能的变化。如果操作增加了势能$\Phi(S) \Phi(S)$则均摊成本上升如果操作消耗了势能$\Phi(S) \Phi(S)$则均摊成本下降。设 $S_1, S_2, \dots, S_m$ 为从初始状态 $S_0$ 开始、经过 $m$ 次操作后产生的状态序列$c_i$ 为第 $i$ 次操作的实际开销则第 $i$ 次操作的均摊成本 $p_i$ 为$$ p_i c_i \Phi(S_i) - \Phi(S_{i-1}) $$因此$m$ 次操作的总时间花销为$$ \sum_{i1}^m c_i \sum_{i1}^m p_i \Phi(S_0) - \Phi(S_m) $$由于 $\Phi(S) \geq \Phi(S_0)$总时间花销的上界为$$ \sum_{i1}^m p_i \geq \sum_{i1}^m c_i $$因此若 $p_i O(T(n))$则 $O(T(n))$ 是均摊复杂度的一个上界。这就是势能分析能给出严格复杂度上界的核心逻辑势能的存储与释放恰好将高成本操作的尖峰抹平。示例动态数组的扩容分析以动态数组vector的插入操作为例定义势能函数$$ \Phi(h) 2n - m $$其中 $n$ 是数组中的元素数量$m$ 是数组的当前容量。这个势能函数反映了数组中剩余可用空间的数量即当前容量与实际使用空间之间的差异。情况一插入操作无需扩容操作成本$O(1)$因为只需插入一个元素。势能变化插入后元素数量增加 $1$势能增加 $2$$$ \Phi(h) - \Phi(h) 2(n1) - m - (2n - m) 2 $$均摊成本$1 2 3$。情况二插入操作触发扩容假设当前容量 $m n$插入一个新元素时触发扩容新容量变为 $2n$。操作成本$O(n)$因为需要将所有元素复制到新数组中并插入新元素。势能变化扩容后容量增加势能减少变化大小为 $2 - n$$$ \Phi(h) - \Phi(h) 2(n1) - 2n - (2n - n) 2 - n $$均摊成本$n 1 (2 - n) 3$。两种情况的均摊成本都是 $3$即 $O(1)$。尽管扩容操作的实际成本高达 $O(n)$但由于势能函数的设计扩容前的满数组积累了 $2n - n n$ 单位的势能恰好抵消复制成本整体均摊成本仍然保持在常数级别。这里也能看出势能分析与记账分析的对应关系势能函数 $\Phi(h) 2n - m$ 中的系数 $2$正是记账法中每次插入预存 $2$ 单位费用的数学化表达。扩展示例堆栈操作的三方法对比堆栈操作是均摊分析的经典应用场景。假设堆栈 $S$ 支持以下三种操作操作说明实际成本 $c_i$S.push(x)将元素 x 入栈$1$S.pop()弹出栈顶元素$1$S.multi-pop(k)弹出栈顶 k 个元素$O(\min(\lvert S\rvert, k))$下面用三种方法分别分析体会它们在同一个问题上各显神通。聚合分析法聚合分析将计算所有操作的总成本并平均分摊到每个操作上。对于 $n_{push}$ 次push(x)每次成本 $O(1)$总成本 $O(n_{push})$对于 $n_{pop}$ 次pop()每次成本 $O(1)$总成本 $O(n_{pop})$对于 $n_{multi-pop}$ 次multi-pop(k)尽管单次实际成本为 $O(\min(\lvert S\rvert, k))$但这些操作弹出的元素数量不会超过之前push(x)的元素数量因此总成本仍受 $n_{push}$ 的约束。由于总操作次数 $n n_{push} n_{pop} n_{multi-pop} \leq 2 \times n_{push}$总成本为 $O(n_{push}) O(n)$每次操作的均摊成本为 $O(n)/n O(1)$。记账分析法记账分析为每次push(x)预留一部分费用以支付未来可能的pop()或multi-pop(k)。S.push(x)假设均摊成本为 $2$其中 $1$ 单位用于当前操作另 $1$ 单位存储为费用用于支付未来的pop()或multi-pop(k)S.pop()实际成本为 $1$但之前的push(x)已为其预存了 $1$ 单位费用因此均摊成本为 $0$S.multi-pop(k)每个弹出的元素的实际成本为 $1$可以由该元素push(x)时预存的费用支付因此均摊成本为 $0$。入栈操作预存的费用足以支付未来该元素的出栈操作因此每次操作的均摊成本为 $O(1)$。注意这里比动态数组的例子更精确费用是绑定到具体元素上的每个元素入栈预存 $1$ 单位恰好覆盖它未来被弹出的 $1$ 单位成本账户严格收支平衡。势能分析法势能分析定义势能函数来衡量堆栈状态并利用势能变化平衡操作成本。势能函数设 $\Phi(h)$ 为堆栈中的元素数量即 $\Phi(h)\lvert S\rvert$每个元素贡献 $1$ 单位势能S.push(x)元素数量增加 $1$势能增加 $1$均摊成本为 $112$S.pop()元素数量减少 $1$势能减少 $1$均摊成本为 $1-10$S.multi-pop(k)弹出 $k$ 个元素势能减少 $k$均摊成本为 $k-k0$。通过以上势能函数设计push(x)的均摊成本为 $2$pop()和multi-pop(k)的均摊成本为 $0$。因此所有堆栈操作的均摊成本均为 $O(1)$。三种方法的异同与选用方法核心手段动态数组均摊成本堆栈均摊成本适用特点聚合分析计算总成本再除以操作数$O(1)$$O(1)$最直观但需要先能算出整个序列的总成本记账分析为操作预存费用余额非负$O(1)$$O(1)$直观体现前置支付适合逐操作解释势能分析定义势能函数 $\Phi$用 $\hat{c}c\Delta\Phi$ 记账$O(1)$$O(1)$最通用、最强大适合复杂的局部操作分析三者对同一问题的结论完全一致动态数组与堆栈的均摊成本均为 $O(1)$这正是它们内在等价性的体现。实际使用中聚合分析适合整体趋势明显的序列记账分析适合逐操作解释费用流向的教学场景而势能分析因为可以对每个操作独立定义 $\hat{c}$不必关心操作之间的顺序细节在证明复杂数据结构的均摊界时最为常用。仓库中的实战案例均摊分析在 OI-wiki 数据结构中的应用均摊分析不是孤立的理论OI-wiki 的数据结构章节中多处直接运用了本文介绍的方法尤其是势能分析来证明复杂度上界。以下案例可以作为延伸阅读印证方法的实战价值并查集路径压缩 按秩合并docs/ds/dsu-complexity.md 是势能分析最硬核的应用。它定义了基于 $\alpha(n)$反阿克曼函数、秩 $\mathit{rnk}(x)$、层级 $\mathit{level}(x)$ 与迭代数 $\mathit{iter}(x)$ 的势能函数通过证明union操作中唯一可能增加势能的点是 $y$最多增加 $\alpha(n)$以及find操作中至少有 $s-\alpha(n)$ 个节点的势能至少减少 $1$最终得出并查集均摊时间复杂度为 $\Theta(\alpha(n))$ 的结论——这正是每次查询几乎常数这一直观印象的严格证明。Splay 树docs/ds/splay.md 用势能分析法推导伸展操作的均摊复杂度。它定义 $w(x)\sum_{y\in subtree(x)} s(y)$ 形式的权重函数逐一分析zig、zig-zig、zig-zag三种旋转操作的均摊成本分别不超过 $3(w(x)-w(x))$ 与 $3(w(x)-w(x))1$证明单次伸展操作均摊复杂度为 $O(\log n)$从而插入、查询、删除均为均摊 $O(\log N)$。替罪羊树docs/ds/sgt.md 利用均摊分析解释为什么偶发重构不拖累整体通过摊还分析可知若每次插入时在自根到节点的路径上每个节点增加 $\Theta(1)$ 势能那么到节点 $x$ 发生子树重构时已在该节点累积了 $\Omega(\lvert T_x\rvert)$ 的势能足以偿还重构成本 $\Theta(\lvert T_x\rvert)$从而 $\Theta(n)$ 次插入的均摊复杂度为 $O(\log n)$。配对堆docs/ds/pairing-heap.md 明确指出配对堆的复杂度基于势能分析的均摊复杂度且正是因为这一点无法可持久化——这从反面印证了均摊分析与最坏情况保证如可持久化所需的单次 $O(\log n)$ 保证之间的区别与本文开篇均摊分析只能确保最坏情况性能的每次操作耗费的平均时间的边界描述遥相呼应。斜堆docs/ds/leftist-tree.md 中斜堆作为左偏树的自适应形式合并时无条件交换路径上的节点根据均摊分析其插入、合并、删除最小值复杂度为 $O(\log n)$。双栈模拟队列docs/ds/queue.md 是均摊分析在基础数据结构中的典型应用——每个元素只会进入/转移/弹出一次均摊复杂度 $O(1)$。该文还讨论了均摊分析的失效边界当某个栈为空时交替查询队首队尾会导致均摊分析失效需要调整转移策略来维持均摊常数时间这对理解均摊分析的适用前提极具价值。LCTLink-Cut Treedocs/ds/lct.md 中Access操作的时间复杂度证明同样依赖势能分析定义势能函数 $\Phi$ 为所有重虚边的数量均摊成本 $c_i t_i \Delta \Phi_i$最终得到Access及Cut、Link、Findroot等操作均摊 $O(\log n)$ 的结论。从这些案例可以总结出一条规律凡是平时攒、关键时花的数据结构都天然适合用均摊分析来刻画——势能函数的设计目标就是让攒与花恰好互相抵消从而把复杂度的尖峰压平为常数。参考资料均摊分析概念与三种方法的原始出处可参见维基百科 Amortized analysis 词条与 Cornell CS 3110 课程 Lecture 20: Amortized Analysis原文档 docs/basic/amortized-analysis.md 末尾所列。本文涉及的前置复杂度概念详见 docs/basic/complexity.md相关数据结构复杂度证明的仓库内延伸阅读路径已在上文逐一给出。【免费下载链接】OI-wiki:star2: Wiki of OI / ICPC for everyone. 某大型游戏线上攻略内含炫酷算术魔法项目地址: https://gitcode.com/GitHub_Trending/oi/OI-wiki创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考