开发杂谈

平摊分析 Amortized Analysis

为什么要平摊分析？

算法往往是会对内存中的数据进行修改的，而同一个算法的多次执行，就会通过对数据的修改而互相影响。

为了解决计算上的困难，以及操作之间的不独立而导致的估算上界过松，我们就需要用到平摊分析。

平摊分析的三种方法

平摊分析总共有三种方法，概括起来就是：

  • 聚集分析：n次总代价 / n
  • 记账法：把之后要做的操作的代价提前考虑
  • 势能法：用势能释放来支付未来操作的代价

其中势能法是我们需要重点掌握的方法。

聚集分析 Aggregate Method

平摊代价 = n次操作总代价 / n

通过总运行时间求平均得到平摊时间，不需要对操作序列的概率分布做假设。

栈S上的三种操作

比如课堂例题，栈上的三种操作(PUSH、POP、MULTIPOP)，我们可以得到一个总时间上界$O(n^2)$，但它并不紧。

在栈上，所有POP和MULTIPOP弹出的对象数不会多余PUSH入栈的对象数。

因此，若进行n次操作，PUSH的总规模是$O(n)$，这也就使得POP和MULTIPOP的总规模也只能是$O(n)$。那么n次操作的总代价为$O(n)$，我们计算得到平摊代价=$\frac{O(n)}{n} = O(1)$

二进制计数器

观察INCREMENT操作序列

  • 每次操作，$A[0]$都反转
  • 每两次操作，$A[1]$反转
  • 每$2^i$次操作，$A[i]$反转
$$ \sum_{i=0}^{\lfloor log(n) \rfloor}{\lfloor \frac{n}{2^i} \rfloor} < n\sum_{i=0}^{\infin}\frac{1}{2^i} = 2n $$

那么总时间为$O(n)$，每个操作平坦时间为$O(n) / n = O(1)$

记账法 Accounting Method

不必算出每一步实际代价，我们用一个虚构的代价，满足对任意k，前k步满足：

$第k步存款 = \sum_{i=1}^{k}平摊代价_i - \sum_{i=1}^k实际代价_i \geq 0$

如何设计平摊代价？提前考虑之后的代价。

栈S上的三种操作

仍然，在栈上，所有POP和MULTIPOP弹出的对象数不会多余PUSH入栈的对象数。

那么我们如何设计平摊代价？答案是把POP类操作的帐记在PUSH头上。

每次PUSH操作，我们对入栈的对象收费2元，1元用于支付实际费用，另1元存起来，为了支付这个对象以后可能发生的POP操作。

由于栈中的对象数不可能为负，而每个对象被POP的次数不会多于它被PUSH的次数，所以存款不会小于0。

那么，我们可以对POP、MULTIPOP收费0元。因为PUSH时已经预先付过它们的费用了。

进行n次操作，PUSH总共记账$O(2n)$，POP和MULTIPOP总共记账$0$，那么总代价也就是$O(2n) = O(n)$。

平摊时间为$O(n)/n = O(1)$。

二进制计数器

注意到，每次INCREMENT只会把一个0反转为1，但可能把多个1反转为0.

我们每次INCREMENT收费2元，其中1元用来支付将一个0反转为1的实际费用，另1元存在这个反转出来的1上，为了支付以后可能发生的反转为0；那么由于之前的存款，每个被反转为0的1上原本都有1元存款，也就支付了这次INCREMENT的费用。

而1的个数总是大于等于0的，所以存款不可能为负。

势能法 Potential Method

利用数据结构$D$的函数$\Phi$定义平摊代价：

$平摊代价_i = 实际代价_i + \Phi(D_i) - \Phi(D_{i-1})$

其中，对于任意$i$，都要满足$\Phi(D_i) \geq \Phi(D_0)$，这样我们就能保证我们给出了实际代价的一个上界。

势能法与记账法有些类似，但是记账法是将存款存储在某些特定的对象之上，而势能法的势能是体现在整个数据结构之上的。

栈S上的三种操作

仍然是栈的三操作，我们定义势函数为栈中对象的个数：

  • 开始时，栈是空的，所以有$\Phi(D_0) = 0$.
  • 栈中对象数始终非负，所以满足$\Phi(D_i) \geq 0 = \Phi(D_0)$.

那么我们就能保证我们给出了实际代价的一个上界。

那么对于作用在一个包含$s$个对象的栈上的第$i$个操作，

  • PUSH

    势能差：$\Phi(D_i) - \Phi(D_{i-1}) = s+1 - s = 1$

    平摊代价：$a_i = c_i + \Phi(D_i) - \Phi(D_{i-1}) = 1+1=2$

  • MULTIPOP(S, k)

    实际代价：$c_i = min(s, k)$

    势能差：$\Phi(D_i) - \Phi(D_{i-1}) = -min(s, k)$

    平摊代价：$a_i = c_i + \Phi(D_i) - \Phi(D_{i-1}) = 0$

  • POP

    同理MULTIPOP，平摊代价也是0.

我们分析出三种栈操作的平摊代价都是$O(1)$，那么n次操作的总平摊代价就是$O(n)$。

而这是总实际代价的一个上界。所以n次操作的最坏时间复杂度为$O(n)$。

二进制计数器

我们定义势函数为数组$A[0…k-1]$中$1$的个数。

设第$i$次INCREMENT操作将$t_i$个1反转为0，那么实际代价为$t_i+1$

设第$i$次操作后，数组中1的个数为$b_i$，那么

  • 如果$b_i = 0$，则第$i$次操作反转了$k$个1，那么$b_{i-1} = t_i = k$
  • 如果$b_i > 0$，那么有$b_i = b_{i-1} - t_i + 1$
  • 这两种情形都满足：$b_i \leq b_{i-1} - t_i + 1$

势能差：$\Phi(D_i) - \Phi(D_{i-1}) \leq (b_{i-1} - t_i + 1) - b_{i-1} = 1 - t_i$

平摊代价：$a_i = c_i + \Phi(D_i) - \Phi(D_{i-1}) = (t_i + 1) + (1- t_i) = 2$

补充习题

INSERT & REMOVE_BOTTOM_HALF

请设计一个数据结构，能够维护一组n个不同整数组成的集合S，能够支持以下两种操作：

  • INSERT(x, S)：将x加入S。
  • REMOVE_BOTTOM_HALF(S)：从S移除最小的$\lceil \frac{n}{2} \rceil$个整数。 描述你的算法并给出最坏情况下两个操作的时间复杂度。采用势能法进行平摊分析，得到两种操作的平摊时间，选择合适的分析策略，令INSERT(x, S)的平摊时间为$O(1)$，REMOVE_BOTTOM_HALF(S)的平摊时间为$0$.

我们用一个无序的数组（或者，动态表）来存放所有的整数。

定义势函数$\Phi(D_i) = k|D_i| = kn$，那么

  • REMOVE_BOTTOM_HALF(S):

    注意到，这步操作我们可以利用算法$Select(n, k)$选出中位数，然后再扫描一遍数组，将保留下来的数字复制到一个新的数组中，然后令S指向这个新的数组头，在实际时间2n内完成。

    但是，为了严谨起见，我们设它是在实际时间$cn$内完成的。其中$c$为大于1的常数。

    我们令$k = 2c$，即$\Phi(D_i) = 2c|D_i| = 2cn \geq 0$，那么

    势能差：$\Phi(D_i) - \Phi(D_{i-1}) = 2c\lfloor \frac{n}{2} \rfloor - 2cn$

    $$ \begin{align} a_i &= c_i + \Phi(D_i) - \Phi(D_{i-1}) \\ &= cn + 2c\lfloor \frac{n}{2} \rfloor - 2cn \\ &= 2c\lfloor\frac{n}{2}\rfloor - cn \\ &\leq 0 \end{align} $$

    所以平摊时间为0.

  • INSERT(x, S)：

    势能差：$\Phi(D_i) - \Phi(D_{i-1}) = 2cn - 2c(n-1) = 2c$

    平摊时间：$a_i = c_i + \Phi(D_i) - \Phi(D_{i-1}) = 1 + 2c = O(1)$

显然，最坏情况下，INSERT操作的时间复杂度为$O(1)$，而根据上述分析，REMOVE_BOTTOM_HALF的最坏时间复杂度为$O(n)$。它们的平摊代价根据上述分析，也分别为$O(1)$与$0$。

[竞争分析] MTF(Move-to-Front) 链表访问

MTF算法

考虑一个问题：

我们有一个线性表（比如单链表），在它上面：

  • 我们访问第$i$个元素的访问代价为$i$

  • 交换两个相邻元素的代价为某个固定常数值

我们的目标是：通过“交换”调整原链表，使得n次访问的总访问代价最小。

如果访问序列是已知的，那么我们当然可以针对这个访问序列设计一个最优的调整策略。 但是，如果我们并不能提前知道访问序列，我们可以考虑采取MTF方式来调整链表。

MTF利用了一个事实：对于现实中的问题，比如分页，如果第$i$个元素在时间$t$被访问，那么它比较有可能在时间$t$的不久后再次被访问。（访问局部性 in ICS）

MTF算法： 当第$i$个元素被访问，我们将它移动到线性表的最前面(Move-to-Front)。 而这个“移动”操作是通过$i-1$次交换完成的。 所以，当第$i$个元素被访问，总代价为$i+ i-1 = 2i-1$

我们可以利用平摊分析证明：

MTF不会比任何其他调整策略（包括最优策略）效率的4倍更差，甚至不需要假设存在访问局部性。

定义势函数

设任意一个调整策略为算法A。我们定义在时刻$t$时的势函数为MTF作用下的链表相对于A作用下的链表的逆序对数的2倍。

比如，在时刻$t$时，MTF的链表为$(a, b, c, e, d)$，A的链表为$(a, b, c, d, e)$，那么此时的势函数结果就是2。

由于初始时，两个算法下的链表都是初始链表，相对逆序对数为0，所以$\Phi(0)=0$。 而在任意时刻下，相对逆序对数都不可能为负值，所以$\Phi(t) \geq \Phi(0)$。 那么我们就能保证我们能给出实际代价的一个上界。

计算平摊代价

现在，我们考虑访问一个元素$x$。设$x$在MTF的链表里在第$k$个位置，在A的链表里在第$i$个位置。我们先假设A并不会交换其他元素。

在MTF算法中，访问元素$x$并交换到前面的总代价为$2k-1$。 在算法A中，访问元素$x$的代价为$i$，设其进行其他操作的代价为$Q$，那么总代价为$i+Q \geq i$。

因为MTF算法将$x$移动到了表前面，而这个$x$之前在MTF的链表中前面有$k-1$个元素，在A的链表中之前有$i-1$个元素，所以它最多增加$\min{k-1, i-1}$个新相对逆序对。与此同时，它最少减少了$k-1-\min{k-1, i-1}$个旧相对逆序对。

而由势函数的定义，势的变化最多为2倍的两者之差，即$4\min{k-1,i-1}-2(k-1)$

$$ \begin{align} c &= a + \Delta\Phi \\ &\leq (2k-1) + 4\min\{k-1, i-1\}-2(k-1) \\ &\leq 4\min\{k-1, i-1\} + 1 \\ &\leq 4i \\ &\leq 4(i+Q) \end{align} $$

也就得出了MTF的平摊代价不会比A的平摊代价的4倍更高。

思考：如果算法A会交换其他元素怎么办？

不妨假设A交换了2个相邻元素。 这并不会影响到MTF的实际代价。这会增加$2$给新势能。 但同时，它也增加了算法A的$Q$部分$1$。 那么，MTF的均摊代价虽然增加了$2$，但是它的界限却增加了$4$，结论仍然成立。

所以，无论A怎么交换其他元素，都不会影响我们的结论。

更多平摊分析经典问题：

  • Splay树
  • 红黑树
  • 斐波那契堆
  • 并查集
  • 最大流 (Push-Relabel 预流推进算法)
  • 动态表 / 哈希表
  • 替罪羊树
算法
Licensed under CC BY-NC-SA 4.0
comments powered by Disqus