势能分析法

定义

在平摊分析中,势能法是一种重要的方法。我们将对数据结构的修改看作“做功”,做功会导致数据结构的势能改变。从技术上来说,对于数据结构 $D$,如果能够定义势能函数 $\Phi(D)$ 并给出一次操作时间开销和势能变化总和的上界:

其中 $T_i$ 是操作时间,$\Delta\Phi$ 是势能变化量即 $\Phi(D’)-\Phi(D)$,$\hat{c}$ 称为平摊开销。那么,对两侧求和便得到:

就有

动态扩增数组问题

给定一个数组,其初始大小为 $1$,支持在数组末尾加入一个元素;如果数组元素已满,则将数组的大小翻倍,并付出线性于新数组长度的时间开销。求操作的平摊复杂度。

我们希望时间开销和势能变化的和有好的上界,因此当付出较大的时间代价时,我们希望势能的变化量也尽可能大。从物理的角度理解,”数组翻倍“这个做功的直接影响是使得数组的空闲区域变多,因此不妨定义势能函数为

那么当数组未满时的平摊开销就是

当数组已满,需要翻倍时,不妨设原先数组长度为 $L$,那么

因此,$n$ 次操作总的时间开销就是

换言之平摊时间开销就是 $O(n)/n = O(1)$,这便完成了分析。

替罪羊树

给定一个常数 $1/2 \le c < 1$,如果对于结点 $x$ 有 $|x.left|, |x.right| \le c|x|$,称结点 $x$ 是 $c$ 平衡的;如果二叉查找树的每一个节点都是 $c$ 平衡的,那么称这个二叉查找树是 $c$ 平衡的。很明显,我们可以在 $O(|x|)$ 的时间复杂度内将 $x$ 子树中所有结点变为 $1/2$ 平衡的,称这个过程为重构

  • 插入:将 $x$ 插入到树中,重构最高的非 $c$ 平衡结点
  • 删除:将 $x$ 标记为删除,当一个子树中有超过一半元素标记为删除后,重构这个子树,并在重构的过程中去掉所有标为删除的结点。

当取 $1/2 <c <1$ 时我们称这样的结构为替罪羊树。

定理:替罪羊树操作均摊时间复杂度为 $O(\log n)$

证明:用归纳法容易证明对于 $1/2\le c < 1$,$c$ 平衡的树树高是 $O(\log n)$ 的,考虑如何分析插入和删除的时间复杂度。重构的契机有两种:树过于不平衡或者等待删除的结点过多,因此势能函数中应该体现这两点。不妨设 $\Delta(x) = ||x.left|-|x.right||$,$M(x)$ 表示子树 $x$ 中被标为删除的结点个数,定义势能函数为

其中 $k$ 是一个用于抵消大 $O$ 隐含常数的常数。

容易发现,对于 $1/2$ 平衡的二叉查找树而言,由于左右孩子的大小不超过 $1$,其势函数 $\Phi(D) = -kM(root)$。

接下来考虑每个操作的平摊开销

  1. 重构:设重构的结点是 $x$,根据定义要么 $M(x)\ge |x|/2$,要么 $x$ 不是 $c$ 平衡的。第一种情况是容易的,因为重构一定可以降低 $\Phi$ 达 $|x|/2$。

    第二种情况下,由于重构不会改变子树关系,因此

    最后一步是由于 $1-2c$ 是小于 $1$ 的常数,因此只需取合适的 $k$ 便可以抵消 $O(|x|)$ 的时间开销。

  2. 插入:由于树高是 $O(\log n)$ 的,插入一个结点仅会影响 $O(\log n)$ 个结点的 $\Delta(x)$,且不超过 $1$,因此平摊开销 $\hat c = O(\log n) + c\times O(\log n) = O(\log n)$

  3. 删除:由于树高是 $O(\log n)$ 的,且仅会增加一个删除结点,因此 $\hat c = O(\log n) + c\times O(1)=O(\log n)$

因此,插入和删除的时间复杂度都具有平摊上界

自组织表

考虑维护一个链表 $L$,支持以下操作:

  • 给定 $x$,从链表头 $L.head$ 开始依次查找直到找到 $x$,付出的时间代价是 $x$ 在链表中的排名 $rank_L(x)$

为了提高查找效率,链表可以做如下修改:

  • 给定两个相邻的元素 $x, y$,将他们交换,花费 $1$ 的时间代价

考虑如下的在线算法:每次访问一个元素时,就将其移动到开头,这样的策略称为 Move to Front(MTF)。

定理:MTF 算法的竞争比是 $4$。

证明:记 MTF 算法为 $M$,最优离线算法为 $OPT$,我们希望用势能函数表征 $M$ 维护的链表 $L_M$ 和最优链表 $L_O$ 之间的“距离”。我们用最小编辑距离(将 $L_M$ 变换到 $L_O$ 的最小操作次数)来表征这一点,根据排序算法的知识很容易知道,最小编辑距离正是逆序对的个数。如果用 $x<_L y$ 表示在序列 $L$ 中 $x$ 在 $y$ 左侧,那么

接下来我们说明,MTF 算法的时间开销与最优算法的时间开销差距不会太大。设 $#Inv$ 表示逆序对个数,$T_i$ 表示最优算法在这一次修改链表的次数,MTF 算法每次操作的平摊开销是

其中第二项表示最优算法移动导致势能变化的上界,后两项的和取决于 MTF 操作新增的逆序对个数。设这次访问的元素为 $x$,将所有元素分为四类:

在 $L$ 中 $x$ 的左侧 在 $L$ 中 $x$ 的右侧
在 $L’$ 中 $x$ 的左侧 $A$ $B$
在 $L’$ 中 $x$ 的右侧 $C$ $D$

那么,消减逆序对个数是 $|C|$,新增逆序对的个数是 $|A|$,那么上式也可以写成

注意到 $|A| + |C| = rank(x)$,化简上面的式子

因此:

取 $c = 2$,注意到 $|A| + |B| = rank_{L_O}(x)$,就有

最后一项正是最优算法单次开销的 $4$ 倍,设操作序列为 $|S|$,就有

这便证明了 MTF 算法的竞争比是 $4$。

斜堆

斜堆是一种可并二叉堆,其维护一个满足堆性质的二叉树,并用合并完成插入、删除操作。其中,合并算法如下:

  • 不妨设合并的两个堆 $A.value < B.value$,递归合并 $A.right, B$,并在结束后交换 $A$ 的左右孩子

定理:斜堆的插入、删除、合并平摊复杂度为 $O(\log n)$

证明:设 $light(u)$ 表示 $u$ 的轻儿子,则

在一次合并操作中,如果右儿子原先是重儿子,则之后右二子变为轻儿子,这带来了 $-c$ 的势能增加;如果右儿子原先是轻儿子,由于递归过程中经过的轻儿子总数是 $O(\log n)$ 的,因此一次合并的平摊代价为 $O(\log n)$。

由于插入操作和删除操作都仅包含 $O(1)$ 的时间和势能变化以及一次合并,因此所有操作的平摊时间复杂度都是 $O(\log n)$ 的。

伸展树

伸展树(Splay)是一种自适应二叉查找树,其特点是每当访问一个元素之后,就将其旋转到根。

旋转到根总是使用双旋操作。

定理:如果总是使用双旋操作旋转到根,访问 Splay 元素的均摊时间复杂度是 $O(\log n)$

证明:我们希望用势能函数的变化量抵消访问元素的时间开销。设 $|u|$ 为结点 $u$ 子树内部元素的大小,定义势能函数 $\Phi(T)$

其中 $w(u) = \log(|u|)$。我们将向下寻找结点的时间复杂度平摊在向上旋转的过程中,因此只需要考虑向上旋转的复杂度。

Zig-Zig

设当前结点是 $u$,双旋的第一种情况如下图所示

graph TB
    subgraph After
    u1(u) --> A1[A]
    u1 --> p1[p]
    p1 --> B1[B]
    p1 --> g1[g]
    g1 --> C1[C]
    g1 --> D1[D]
    end
    subgraph Before
    g --> p
    p --> u(u)
    u --> A
    u --> B
    p --> C
    g --> D
    end

操作前后的势能差为

设 $T$ 为上图所有点构成的树,注意到

因此

Zig-Zag

graph TB
    subgraph After
    u1(u) --> p1[p]
    p1 --> A1[A]
    p1 --> B1[B]
    u1 --> g1[g]
    g1 --> C1[C]
    g1 --> D1[D]
    end
    subgraph Before
    g --> p
    p --> A
    p --> u(u)
    u --> B
    u --> C
    g --> D
    end

势能变化量为

因此平摊开销为

Zig

graph TB
    subgraph After
    u1(u) --> A1[A]
    u1(u) --> p1[p]
    p1 --> B1[B]
    p1 --> C1[C]
    end
    subgraph Before
    p --> u
    u(u) --> A
    u --> B
    p --> C
    end

势能变化量为

平摊开销为

访问开销

根据算法,一次访问包含一次 Zig 和多次 Zig-Zag、Zig-Zig,总的平摊开销为

因此平摊时间复杂度正是

只需 $m\ge n$。

本文标题:势能分析法

文章作者:ljt12138

原始链接:http://ljt12138.github.io/2019/08/05/potential_analysis/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。