数据结构与算法分析读书笔记系列11-摊还分析

Table of Contents

1 摊还分析

考虑任意顺序的M次操作的最坏运行时间。

一种数据结构（例如：伸展树），在任意顺序的M次操作（总共）花费O（MlogN）最坏情形时间。因此长时期运行这种数据结构的行为就像每次操作花费O（logN）时间一样。我们把它称为摊还时间界（amortized time bound）。

2 一个无关的智力问题

有时间间接求解一个问题要比直接求解容易。我们将这个思路用于将要进行的摊还分析。我们引入一个附加变量，叫做位势（potential），有了它，我们能够证明以前很难证明的一些结果。

3 二项队列

二项树B0 是一个单节点树，对于k > 0，二项树Bk 通过将两颗二项树Bk-1 合并到一起而得到。一颗二项树的节点的秩（rank树节点容量的度量）等于它的儿子节点的个数，特别地。Bk 的根节点的秩为k。

最重要的操作是merge（合并）。

插入操作通过创建一个单节点二项队列并执行一次merge来完成。

在BuildBinomialQueue例程运行期间，每一次插入有一个最坏情形运行时间O(logN)，但是由于整个例程最多用到2N个单位的时间，因此这些插入的行为就像是每次使用不多于两个单位的时间。

摊还分析的一般技巧：

数据结构在任一时刻的状态由一个称为位势（potential）的函数给出。这个位势函数不由程序保存，而是一个计数装置，该装置帮助进行分析。当一些操作花费少于我们允许他们使用的时间时，则没有用到的时间就以一个更高位势的形式“存储”起来。当操作出现超出规定的时间时，则超出的时间通过位势的减少来计算。可以把位势看作是一个储蓄账户。

好的位势函数所具有的一些性质：

  • 总假设它的最小元位于操作序列的开始处。选择位势函数的一种常用方法是保证位势函数初始值位0，而且总是非负的。
  • 消去实际时间中的一项。

二项队列操作完整的分析。

定理

Insert、DeleteMin以及Merge对于二项队列的摊还运行时间分别是O(1)、O(logN)和O(logN)。

证明

位势函数是树的棵树。初始的位势函数为0，且位势总是非负的，因此摊还时间是实际时间的一个上届。对于Merge，假设两棵树分别有N1 和N2 个节点以及对应的T1 和T2 棵树。令N = N1 + N2 。执行合并的实际时间为O(log(N1 ) + log(N2 )) = O(logN)。在合并之后，最多存在logN棵树，因此位势最多可以增加O(logN)。这就给出一个摊还的界O(logN)。DeleteMin的界可用类似的方法得到。

4 斜堆

斜堆（Skew heap）也叫自适应堆（self-adjustion heap），它是左式堆的一个变种。和左式堆一样，它通常也用于实现优先队列。它的合并操作的时间复杂度也是O(logn)。

相比于左式堆，斜堆的节点没有“零距离”这个属性：除此之外，它们斜堆的合并操作也不同，斜堆merge操作后，不需要考虑左右子堆的零路径大小，而是无条件交换左右子堆。

对于斜堆，我们知道关键的操作是合并。为了合并两个斜堆，我们把它们的右路径合并使之成为新的左路径。对于新路径上的每一个节点，除去最后一个外，老的左子树作为右子树而赋于其上。在新的左路径上的最后节点已知没有右子树，因此给它一颗右子树就不明智了。

斜堆的合并操作算法如下：

  1. 如果一个空斜堆与一个非空斜堆合并，返回非空斜堆；
  2. 如果两个斜堆都非空，那么比较两个根节点，取较小堆为新的根节点。将“较小堆的根节点的右孩子”和“较大堆”进行合并。
  3. 合并后，交换新堆根节点的左孩子和右孩子。

位势函数 轻节点/重节点

一个节点p如果其右子树的后裔数至少是该p的后裔总数的一半，则称节点p是重的，否则称之为轻的。注意，一个节点的后裔个数包括该节点本身。

我们将要使用的位势函数是这些堆（的集合）中重节点的个数。

由于Insert和DeleteMin操作基本就是一些Merge，它们的摊还界也是O(logN)。

5 斐波那契堆

我们可以使用优先队列改进Dijkstra最短路径算法的粗略运行时间O(|V|2)。重要的现象是运行时间被|E|次DecreaseKey操作和|V|次Insert和DeleteMin操作所控制。这些操作发生在大小最多为|V|的集合上。通过使用二叉堆，所有这些操作花费O(log|N|)时间，因此Dijkstra算法最后的界可以减到O(|E|log|V|)。

为了降低这个时间界，必须改进执行DecreaseKey操作所需的时间。通过d-堆给出对于DecreseKey操作以及Insert的O(logd |V|)时间界，但对于DeleteMin的界却是O(dlogd |V|)。通过选择d来平衡带有|V|次DeleteMin操作的|E|次DecreaseKey操作的花费，并考虑到d必须总是至少为2，那么我们看到d的一个好的选择是d=max(2,(|E|/|V|))。

它把dijkstra算法的时间界改进到O(|E|log(2+(|E|/|V|)) |V|)。

斐波那契堆是以O(1)摊还时间支持所有基本的堆操作的一种数据结构，但DeleteMin和Delete除外，它们花费O(logN)的摊还时间。我们立即得出，在Dijkstra算法中的那些堆操作将总共需要花费O(|E| + |V|log|V|)的时间。

斐波那契堆是由一组最小堆有序树组成，其中每棵树都必须符合最小堆属性。简单点，斐波那契堆是由一组有点特别的树组成。

斐波那契堆（Fibonacci heap）通过添加两个新的观念推广了二叉堆：

DecreaseKey的一种不同的实现方法 ：我们以前看到的那种方法是把元素朝向根节点上滤。对于这种方法似乎没有理由期望O(1)的摊还时间界，因此需要一种新的方法。

懒惰合并（lazy merging） 只有当两个堆需要合并时才进行合并。这类似于懒惰删除。对于懒惰合并，Merge是低廉的，但是因为懒惰合并并不实际把树结合在一起，所以DeleMin操作可能遇到许多的树，从而使这种操作的代价高昂。

5.1 切除左式堆中的节点

在二叉堆中，DecreaseKey操作是通过降低节点的值然后将其朝着根上滤直到建成堆序来实现的。在最坏的情形下，它花费O(logN)时间，这是平衡树中通向根的最长路径长。

如果代表优先队列的树不具有O(logN)的深度，那么这种方法不适应。例如，若将这种方法用于左式堆，则DecreaseKey操作可能花费𝛩(N)时间。解决的办法是把堆沿着虚线切开，如此得到两棵树，然后再把这两棵树合并成一棵树。

如果切断之后得到的两棵树都是左式堆，那么他们可以以时间O(logN)合并，整个操作也就完成了。然而，这种方案似乎还是行不通，因为T2 未必是左式堆。不过容易恢复到左式堆的性质。

5.2 二项队列的懒惰合并

这个想法如下：为了合并两个二项队列，只要把两个二项树的表连在一起，结果得到一个新的二项队列。这个新的二项队列可能含有相同大小的多棵树，因此破坏二项队列的性质。为了保持一致性，我们将把它称为懒惰二项队列（lazy binomial queue）。这是一种快速操作，该操作总是花费常数（最坏情形）时间。一次插入通过创建一个单节点二项队列并将其合并而完成。区别在于合并是懒惰的。

DeleteMin操作要麻烦得多，因为此处需要我们最终把懒惰二项队列转变回到标准的二项队列，不过，正如我们将要证明的，它仍然花费O(logN)的摊还时间，而不像以前是O(logN)的最坏情形时间。为了执行DeleteMin，我们找出（并最终返回）最小元素。如前所述，我们将它从队列中删除，使得它的每个子节点都成为一颗新的树。此时我们通过合并两棵相等大小的树直至不再可能合并为止而把所有的树合并成一个二项队列。

5.3 斐波那契堆操作

斐波那契堆将左式堆DecreaseKey操作与懒惰二项队列Merge操作结合起来。不过，我们不能一点修改也不做而使用这两种操作。问题在于，如果在这些二项树中进行任意切割，那么结果得到的森林将不再是二项树的集合。因此，每棵树的秩最多为LogN将不再成立。由于在懒惰二项队列中DeleteMin的摊还时间已被证明是2logN+R，因此，对于DeleteMin的界我们需要R = O(logN)成立。

为了保证R = O(logN)，我们对所有的非根节点应用下述法则：

  • 将第一次（因为切除而）失去一个子节点的（非根）节点做上标记。
  • 如果被标记的节点又失去另外一个儿子节点，那么将其从它的父节点切除。这个节点现在变成一颗分离的树的根并且不再被标记。这叫做一次级联切除（cascading cut），因为在一次DecreaseKey操作中可能出现多次这样的切除。

斐波那契堆对于Insert、Merge和DecreaseKey的摊还时间界均为O(1)，而对于DeleteMin则是O(logN)。

位势是斐波那契堆的集合中树的棵树加上两倍的标记节点树。

6 伸展树

树的搜索效率与树的深度有关。二叉搜索树的深度可能为n，这种情况下，每次搜索的复杂度为n的量级。AVL树通过动态平衡树的深度，单次搜索的复杂度为log(n)。对于伸展树（splay tree），m次连续搜索操作有很好的效率。

对某项X进行访问之后，一步展开通过下述三种一系列的树操作将X移至根处：单旋转（zig）、之字形（zig-zag）旋转和一字型（zig-zig）旋转。我们约定：如果节点X执行一次树的旋转，那么旋转前P是它的父节点，G是它的祖父节点（若X不是根的儿子的话）。

位势函数φ 定义为

φ(T) = ∑iT logS(i)

其中S(i)代表i的后裔的个数（包括i自身）。这个位势函数是对树T所有节点i所取的S(i)的对数和。

为简化记号，我们定义：

R(i) = logS(i)

这使得

φ(T) = ∑iT R(i)

R(i)代表节点i的秩。在不同的数据结构中，秩的意义多少有些不同，不过，秩一般地是指树的大小的对数的阶（幅度，magnitude）。对于具有N个节点的一棵树T，根的秩就是R(T) = logN。用秩的和作为位势函数类似于使用高度的和作为位势函数。重要的差别在于，当一次旋转可以改变树中许多节点的高度时，却只有X、P、和G的秩发生改变。

7 总结

这一部分看到摊还分析是如何用于在一些操作间分配负荷。为了进行分析，我们构建一个虚构的位势函数，这个位势函数度量系统的状态。高位势的数据结构是易变的，它建立在相对低廉的操作之上。

一次操作的摊还时间等于实际时间和位势变化的和。整个操作序列的摊还时间等于总的序列操作时间加上位势的净变化。

选择位势函数的关键在于保证最小的位势要产生在算法的开始，并使得位势对于低廉的操作增加而对高昂的操作减少。重要的是过剩或节省的时间要由位势中相反的变化来度量。