★ FEATURED ARTICLE 1. 摊还分析到底在解决什么问题第一次接触摊还分析是在做一个动态数组扩容的性能优化。当时测试同学反馈某个批量导入功能偶尔会卡顿几百毫秒但平均下来每次操作又很快。我盯着代码看了半天发现罪魁祸首是数组满了之后的一次性扩容复制。单次扩容确实慢但你不能说这个操作慢因为绝大多数插入都是O(1)的。这种偶尔很贵、平均很便宜的场景就是摊还分析要处理的核心问题。摊还分析Amortized Analysis不是算平均时间复杂度。平均复杂度通常假设输入服从某种概率分布而摊还分析不依赖概率假设它保证的是在最坏情况下一系列操作的总代价除以操作次数得到的上界。换句话说它给的是一个确定性保证不是统计意义上的期望。这个区别很关键。比如哈希表平均复杂度分析会说假设哈希函数均匀分布查找是O(1)。但摊还分析会说无论哈希函数怎么分布只要每次扩容翻倍n次插入的总代价是O(n)摊还每次O(1)。后者是铁板钉钉的结论前者依赖假设。摊还分析适合谁来学我的判断是写过动态数组、哈希表、并查集、伸展树这类数据结构的开发者或者需要做性能容量规划的后端工程师。如果你只是调用现成的库可能感受不深但一旦你要自己实现一个带扩容的容器或者要评估某个操作序列的总体开销摊还分析就是绕不过去的基本功。它解决的典型问题包括动态数组扩容为什么可以认为是O(1)插入、并查集的路径压缩为什么几乎常数时间、单调栈为什么整体是线性的、splay树的每次操作为什么摊还O(log n)。这些问题用普通的最坏情况分析会得出过于悲观的结论用平均分析又不够严谨摊还分析正好补上这个缺口。2. 三种主流方法的核心思路拆解摊还分析有三套常用工具聚合分析、记账法、势能法。它们得出的结论往往一致但切入角度不同。选哪个方法取决于你觉得哪种更容易讲清楚代价的转移过程。2.1 聚合分析法先算总账再摊到每次聚合分析是最直观的一种。思路是把连续n个操作看成一个整体算出总代价T(n)然后摊还代价就是T(n)/n。它不关心单次操作贵不贵只关心一整套操作下来总共花了多少。拿动态数组举例。假设初始容量为1每次满了就翻倍。n次插入操作扩容发生在第1、2、4、8...次插入时。每次扩容的复制代价分别是1、2、4、8...总复制代价是124...2^k其中2^k是不超过n的最大2的幂这个等比数列求和小于2n。加上n次插入本身的基础代价n总代价T(n) 3n所以摊还每次插入是O(1)。这个推导里有个容易踩的坑很多人会忘记把基础插入代价算进去只算复制代价得出摊还O(1)但过程不完整。严谨的写法是总代价插入代价复制代价两者都是O(n)量级合起来还是O(n)。聚合分析的优点是简单直接不需要什么技巧。缺点是当操作类型多样、代价模式复杂时算总账会变得很困难。比如并查集你很难直接写出n次操作的精确总代价表达式这时候就需要换方法。2.2 记账法给便宜操作预存信用记账法的思路很像公司财务每次操作实际花的钱叫实际代价但我们给它记一个摊还代价。如果摊还代价大于实际代价多出来的部分就存进一个信用账户如果摊还代价小于实际代价就从账户里取钱补上。只要保证账户余额永远不为负那么总摊还代价就是总实际代价的上界。还是动态数组。我们给每次插入记3块钱的摊还代价1块用于本次插入2块存起来。当扩容发生时需要把旧元素复制到新数组每个旧元素复制一次。关键来了每个元素在被插入时都存了2块钱而它一生中最多被复制一次因为每次扩容后容量翻倍元素被复制到新数组后下次扩容时它又会被复制等等这里需要仔细。实际上一个元素从插入到最终被丢弃可能经历多次扩容复制。但记账法的巧妙之处在于我们让每次插入存的钱专门用于支付这个元素未来被复制的费用。由于每次扩容时旧数组里所有元素都要复制而每个元素在插入时都存了足够支付一次复制的信用所以扩容时账户里正好有足够的钱。更严谨的版本是每次插入存2块扩容时每个元素复制花1块账户余额始终非负。记账法的难点在于设计摊还代价。存多了浪费存少了账户会透支。我个人的经验是先观察哪些操作是昂贵的然后倒推便宜操作需要存多少才能覆盖。这个过程有点像解方程需要一点直觉和试错。2.3 势能法用势能函数刻画积蓄的能量势能法是三种方法里最优雅但也最抽象的。它定义一个势能函数Φ把数据结构的当前状态映射成一个非负实数。摊还代价 实际代价 ΔΦ其中ΔΦ是操作前后势能的变化。只要Φ始终非负总摊还代价就是总实际代价的上界。动态数组的势能函数可以定义为Φ 2 * size - capacity其中size是当前元素个数capacity是当前容量。这个函数在扩容前会达到最大size capacity时Φ capacity扩容后容量翻倍Φ变成2size - 2capacity 2capacity - 2capacity 0假设扩容时sizecapacity。所以扩容操作的ΔΦ是负的摊还代价 实际代价 ΔΦ capacity (0 - capacity) 0看起来扩容不花钱了因为势能被释放了。而普通插入的ΔΦ是2摊还代价 1 2 3。势能法的好处是它把积蓄这个概念数学化了。势能高意味着数据结构处于紧张状态未来操作可能要释放能量。势能低意味着结构很松弛未来操作可以积累势能。设计势能函数是势能法的核心难点通常需要你对数据结构的紧张程度有直觉。三种方法没有优劣之分只有适不适合。聚合分析适合操作模式单一的场合记账法适合代价转移关系清晰的场合势能法适合需要严格数学证明的场合。实际工作中我通常先用聚合分析快速估算如果结论不够紧或者证明不优雅再换记账法或势能法。3. 动态数组扩容的完整摊还推导动态数组是摊还分析最经典的案例没有之一。我把它拆成几个层次来讲从最朴素的翻倍扩容到更复杂的增长因子选择再到缩容的坑。3.1 翻倍扩容的摊还代价计算假设数组初始容量为1每次插入时如果size等于capacity就申请一个容量翻倍的新数组把旧元素全部复制过去。我们要证明n次插入的摊还代价是O(1)。用聚合分析。设第i次插入的实际代价为c_i。如果不需要扩容c_i 1只写入一个元素。如果需要扩容c_i 1 size写入新元素加上复制旧元素。扩容发生在size为1、2、4、8...时。总代价T(n) Σc_i n基础插入 Σ(扩容时的复制量)。扩容时的复制量分别是1、2、4、...、2^k其中2^k ≤ n 2^(k1)。这个等比数列的和是2^(k1) - 1 2n。所以T(n) n 2n 3n摊还每次插入 3即O(1)。这里有个细节初始容量为1时第一次插入就触发扩容复制量是0旧数组为空然后容量变成2。第二次插入不扩容第三次插入触发扩容复制量是2。所以复制序列是0、2、4、8...总和仍然小于2n。不影响结论。如果用记账法给每次插入记3块钱1块用于本次写入2块存起来。扩容时每个旧元素复制需要1块而每个旧元素在插入时都存了2块所以账户里有足够的钱支付复制。账户余额始终非负摊还代价是3。如果用势能法Φ 2size - capacity。普通插入实际代价1ΔΦ 2摊还代价3。扩容插入实际代价1 sizeΔΦ (2(size1) - 2capacity) - (2size - capacity) 2 - capacity因为扩容前size capacity。摊还代价 1 size 2 - capacity 1 capacity 2 - capacity 3。三种方法都得到3互相印证。3.2 增长因子为什么不能随便选有人会问为什么一定要翻倍每次扩容加固定大小行不行比如每次满了就加10个位置。我们来算一下。假设每次扩容增加常数c个位置。n次插入扩容次数约为n/c次每次扩容复制当前所有元素。第j次扩容时元素个数约为jc复制代价为jc。总复制代价 Σ(j*c) for j1 to n/c c * (n/c)(n/c1)/2 ≈ n²/(2c)。总代价T(n) n n²/(2c)摊还每次插入是O(n)。这就退化了每次插入摊还代价随n线性增长。所以增长因子必须是乘法性的不能是加法性的。那为什么是2而不是1.5或3这涉及空间和时间的权衡。增长因子越大扩容次数越少复制总代价越小但浪费的空间越多。增长因子越小空间利用率越高但复制越频繁。理论上任何大于1的常数因子都能保证摊还O(1)。但实际工程中2是一个常见选择因为它在空间浪费和复制频率之间取得了不错的平衡。有些实现用1.5比如某些标准库的vector目的是让之前释放的内存块可以被后续扩容复用减少内存碎片。这个细节在内存分配器层面有影响值得注意。3.3 缩容操作的摊还陷阱扩容讲完了缩容才是真正容易翻车的地方。假设我们规定当size降到capacity的1/4时把容量减半。为什么是1/4而不是1/2如果用1/2会出现抖动size在capacity/2附近反复增减导致频繁扩容和缩容每次都要复制大量元素摊还代价退化。用1/4可以避免这个问题。当size降到capacity/4时缩容到capacity/2缩容后size capacity/2正好是新的capacity的一半。如果接下来又插入需要等到size再次达到capacity才会扩容中间有足够的缓冲。这个滞后策略hysteresis是缩容设计的关键。用势能法分析缩容Φ 2*size - capacity当size ≥ capacity/2时或者Φ capacity/2 - size当size capacity/2时。这个分段函数保证Φ始终非负且缩容时ΔΦ为负摊还代价仍然有界。具体推导略繁琐但结论是只要缩容阈值和扩容阈值之间有足够间隔摊还代价仍然是O(1)。我踩过的坑早期实现过一个队列用数组加头尾指针满了就扩容空了就缩容缩容阈值设成1/2。结果在生产者-消费者模式下队列长度在阈值附近波动导致CPU大量消耗在扩容缩容的复制上。后来把缩容阈值改成1/4问题消失。这个教训让我明白摊还分析不只是理论它直接指导工程参数的选择。4. 并查集与单调栈的摊还实战动态数组只是开胃菜。摊还分析真正发光的地方是那些用普通最坏情况分析会得出悲观结论、但实际上非常高效的数据结构。并查集和单调栈是两个典型代表。4.1 并查集路径压缩的摊还上界并查集支持两种操作find找根和union合并。朴素实现下find的最坏情况是O(n)比如一条长链。但加上路径压缩find时把路径上所有节点直接连到根和按秩合并union时把矮树接到高树上n次操作的摊还代价是O(α(n))其中α是反阿克曼函数增长极慢对于任何实际输入都小于5。这个结论的证明是摊还分析里最复杂的之一通常用势能法。势能函数定义为Φ Σ rank(x)其中rank是节点的高度上界。路径压缩会降低某些节点的rank释放势能用来支付压缩路径的实际代价。按秩合并保证树高不超过log n进一步限制势能增长。实际写代码时你不需要记住证明细节但要知道路径压缩和按秩合并必须一起用才能达到O(α(n))。只用路径压缩摊还代价是O(log n)只用按秩合并最坏是O(log n)。两者结合才有几乎常数的效果。我见过有人只写路径压缩然后困惑为什么在大数据量下还是慢。原因就是没有按秩合并树高可能达到O(log n)路径压缩虽然能缓解但摊还上界不够紧。加上按秩合并后性能提升非常明显。4.2 单调栈的整体线性代价单调栈用于解决下一个更大元素这类问题。朴素做法是对每个元素向左或向右扫描最坏O(n²)。单调栈的做法是维护一个单调递减的栈每个元素最多入栈一次、出栈一次。摊还分析用聚合分析最直接n个元素每个元素入栈一次代价1出栈一次代价1总代价2n摊还每次操作O(1)。虽然单次操作可能弹出多个元素但弹出操作的总次数被入栈次数限制不会超过n。这个分析的关键在于每个元素的生命周期内入栈和出栈各一次。你不能只看某次操作弹出了k个元素就说它是O(k)因为那些被弹出的元素以后不会再被弹出了。把视角拉长到整个操作序列总代价就是线性的。单调栈的摊还分析很直观但实际写代码时容易出错的地方是边界条件。比如栈为空时的处理、相等元素是否弹出取决于题目要求严格大于还是大于等于。这些细节不影响摊还结论但影响正确性。4.3 伸展树的摊还对数代价伸展树Splay Tree是一种自调整二叉搜索树每次访问后把访问节点旋转到根。单次操作最坏是O(n)但摊还代价是O(log n)。证明用势能法势能函数基于节点的子树大小对数之和。伸展树的摊还分析比较绕但它的工程价值在于频繁访问的节点会靠近根适合有局部性访问模式的场景。比如缓存实现最近访问的数据再次访问的概率高伸展树能自动优化。不过伸展树在实际中用的不多因为它的常数因子较大而且单次操作可能很慢不适合对延迟敏感的场景。但作为摊还分析的案例它非常经典值得理解。5. 摊还分析常见误区与排查清单摊还分析的概念不难但实际用起来容易掉进几个坑。我整理了一份速查表都是我自己或身边同事踩过的。误区表现正确做法把摊还当平均认为摊还O(1)意味着每次操作都很快摊还O(1)只保证总代价有界单次可能很慢忽略势能非负势能法证明中Φ出现负值必须验证Φ在所有状态下非负记账法账户透支摊还代价设计不当账户余额为负重新设计摊还代价确保每步余额≥0缩容阈值太激进容量在阈值附近抖动缩容阈值应远小于扩容阈值如1/4增长因子用加法每次扩容加固定大小必须用乘法因子否则摊还退化混淆最坏与摊还用最坏情况分析否定摊还结论两者视角不同摊还看序列总代价除了表格里的还有几个经验性的注意事项。第一摊还分析的前提是操作序列。单独看一次操作摊还代价没有意义。你不能说这次插入的摊还代价是3只能说n次插入的摊还代价是3n。这个视角转换是初学者最容易迷糊的地方。第二势能函数的设计需要练习。我刚开始学的时候总是设计出负的势能或者势能变化和实际代价对不上。后来发现一个技巧先想清楚数据结构的紧张状态是什么紧张时势能高松弛时势能低。比如动态数组满了就是紧张扩容后就松弛了。第三摊还分析不改变单次操作的最坏情况。动态数组扩容那一次就是O(n)你不能因为摊还O(1)就忽略这个尖峰。对延迟敏感的系统可能需要用增量扩容或预分配来平滑这个尖峰。这是摊还分析的局限性要清楚。第四实际工程中摊还分析常用来做容量规划。比如你知道每秒有10万次插入摊还每次代价是3个基本操作那每秒就是30万次基本操作据此估算CPU需求。这个换算在性能评估时很有用。6. 从理论到代码的落地建议理论讲完了最后说说怎么在代码里用上摊还分析的思维。写动态数组时增长因子选2或1.5缩容阈值选1/4这是经过验证的稳妥参数。如果你有特殊的内存约束可以调整但要重新做摊还分析确保不会退化。我一般会在注释里写明这些参数的选择理由方便后来人理解。写并查集时路径压缩和按秩合并都要有。路径压缩用递归或迭代都行迭代版本避免栈溢出。按秩合并用rank数组初始为0合并时矮树接高树相等时rank加1。这两行代码是并查集性能的关键别省。写单调栈时注意栈里存索引还是存值。存索引更通用因为可以通过索引访问值和位置。弹出条件根据题目要求写清楚是严格大于还是大于等于这个细节影响结果正确性。做性能测试时不要只测单次操作要测操作序列。用不同规模的数据跑观察总耗时是否随n线性增长。如果发现超线性可能是摊还分析的前提被破坏了比如增长因子写成了加法。我个人的体会是摊还分析最大的价值不是让你会做证明题而是让你在设计数据结构和评估性能时有一个更准确的思维框架。你知道哪些操作可以赊账哪些必须现结这样在优化时就能抓住重点。比如动态数组的扩容复制可以赊账但哈希冲突的探测不能赊账因为每次冲突都是实打实的比较。分清这两类代价优化方向就清晰了。最后分享一个小技巧当你觉得某个操作序列的总代价难以直接计算时试试找找有没有每个元素一生中被处理常数次这样的性质。如果有摊还分析往往能给出漂亮的线性或对数上界。这个性质在栈、队列、并查集、KMP等很多地方都出现是识别摊还场景的一个信号。
阅读完成 · 觉得有帮助？
