复杂度的均摊分析法

动态数组的尾插push_back有时会触发扩容一旦扩容就要申请更大的内存、搬运旧元素、再插入新元素。某一次操作的代价完全可能是 O(n)O(n)但是动态数组尾插的复杂度是均摊 O(1)O(1)类似的现象其实非常多单看某一次操作它们都可能很贵但把它们放到足够长的操作序列里平均到每一步复杂度却仍然很低。均摊分析研究的正是这种现象。平均情况分析 vs 均摊分析均摊分析和平均情况分析average-case analysis不是同一个概念。平均情况分析通常要假设输入服从某种概率分布然后计算期望成本。比如快速排序的平均复杂度分析核心就在于对输入或主元分布做假设。例如快速排序平均是 O(nlog⁡n)O(nlogn) 的但最坏可能是平方复杂度。均摊分析则不同。它不依赖概率和输入一个 vector 无论怎样尾插均摊复杂度也是 O(1)O(1) 。我们可以定义对于一个数据结构的一段操作序列σ(o1,o2,…,om),σ(o1​,o2​,…,om​),如果总实际成本是C(σ)∑i1mci,C(σ)i1∑m​ci​,能否证明存在某个函数 f(m)f(m)使得C(σ)≤m⋅f(m)。C(σ)≤m⋅f(m)。如果可以那么就说这类操作的均摊复杂度是 f(m)f(m)。可以理解为均摊分析给出的是“整段序列的总账不贵”的承诺。于是均摊 O(1)O(1) 并不意味着每次操作都只花常数时间它真正的含义是在任意长的合法操作序列里总成本相比操作次数的复杂度没有那么高。经典例子动态数组动态数组是本文最好的主线。假设一个动态数组有两个状态量size当前元素个数capacity当前容量执行push_back(x)时若size capacity直接写入成本记为 11若size capacity则申请一个两倍大的新数组把旧元素全部搬过去再插入新元素。若旧容量为 kk那么这次成本记为 k1k1。单次最坏显然是线性的但长期看却是均摊常数。下面分别用三种方法来理解它。聚合法直接算前 nn 次操作的总成本聚合法直接计算多步的总成本。由于每次扩容是两倍数组容量会按 1,2,4,8,…1,2,4,8,… 这样翻倍增长。做完前 nn 次插入时普通写入本身一共发生了 nn 次成本是 nn。除此之外还会发生若干次扩容搬运搬运量依次是 124⋯2k−1,124⋯2k−1,其中 2k−1n≤2k2k−1n≤2k 。于是124⋯2k−12k≤2n。124⋯2k−12k≤2n。所以总成本满足C(n)≤n2n3n。C(n)≤n2n3n。也就是说前 nn 次push_back的总成本是 O(n)O(n)因此平均到每次操作复杂度就是 O(1)O(1)。这个证明非常重要因为它第一次把“偶尔很贵”和“长期很便宜”这两个看似矛盾的结论接起来了。扩容确实贵但扩容发生得足够稀疏所以总账仍然可控。记账法平时多收一点留着给扩容买单记账法比聚合法更有“预算”的味道。我们不直接算总账而是假装给每次操作都规定一个均摊收费标准。还是看动态数组尾插。设每次push_back都收费常数代价 33。如果这次没有扩容真实成本只有 11那就剩下 22 存起来如果这次触发扩容就从之前存下来的余额里支付搬运成本。为什么这个方案可行考虑一次从容量 mm 扩到 2m2m 的扩容。在这次扩容发生前数组已经经历了从半满到装满的一系列普通插入。也就是说每次扩容时前面都有发生了足够多大约 m/2m/2 的便宜插入每次都能攒出足够余额总共可以积累出足以覆盖这次搬运的资金。势能法从记账的思想更进一步我们就可以引出势能法。它的思想是给数据结构状态 DiDi​ 定义一个势能函数 Φ(Di)Φ(Di​)然后把第 ii 次操作的均摊成本定义为c^iciΦ(Di)−Φ(Di−1)。c^i​ci​Φ(Di​)−Φ(Di−1​)。这里cici​ 是第 ii 次操作的真实成本c^ic^i​ 是我们定义出来的均摊成本Φ(Di)−Φ(Di−1)Φ(Di​)−Φ(Di−1​) 表示状态势能的变化。这样一次操作的均摊成本就是他的实际成本 势能变化如果我们能选取出合适的势能函数表示当前状态要保证势能始终非负并且初始势能为 00那么对前 mm 次操作有∑i1mc^i∑i1mciΦ(Dm)−Φ(D0)≥∑i1mci。i1∑m​c^i​i1∑m​ci​Φ(Dm​)−Φ(D0​)≥i1∑m​ci​。所以只要每一步的均摊成本都有常数上界那么真实总代价也就有同阶上界。对动态数组一个经典势能函数是Φ2⋅size−capacity。Φ2⋅size−capacity。这个定义的直觉是数组越接近装满也就越接近下一次扩容势能越大。对于不扩容的普通插入。真实成本 1势能变化 2因为size增加 1而capacity不变均摊代价 3对于触发扩容的插入。插入前size mcapacity m势能是 ΦoldmΦold​m插入后size m1capacity 2m势能变成Φnew2(m1)−2m2。Φnew​2(m1)−2m2。这次真实成本是搬运 mm 个旧元素再插入新元素共 m1m1势能变化是 ΔΦ2−m。ΔΦ2−m。。所以均摊成本为 33不扩容时是 33扩容时还是 33。因此动态数组尾插的均摊复杂度就是 O(1)O(1)。其他常见例子栈的MULTIPOP考虑一个支持三种操作的栈PUSH(x)压栈成本为 11POP()弹栈成本为 11MULTIPOP(k)连续弹出最多 kk 个元素成本等于实际弹出的元素数。单看一次MULTIPOP(k)它当然可能要弹很多元素代价不是常数。但如果看一整段操作序列总弹出次数其实不可能超过总压栈次数。因为每个元素最多只会被压入一次、弹出一次。因此如果总共有 mm 次操作那么所有弹栈动作加起来不会超过线性级别于是总成本是 O(m)O(m)均摊每次仍是 O(1)O(1)。这个例子特别适合作为均摊分析的第一个训练只要能发现“每个元素最多被贵处理一次”总成本往往就很好控制。二进制计数器的自增再看一个更经典的例子。一个二进制计数器不断执行INCREMENT一次操作的成本定义为被翻转的位数。