平摊分析

Tip

这是我在北京大学算法设计与分析课上所作的一次课堂报告。

动态表

题目

分别给出使用下列策略的动态表的插入与删除操作的平摊复杂度以及势能函数定义.

1. 元素满时扩大 1 倍空间, 元素不足 1/3 时减少 1/2 空间.
2. 元素满时扩大 1/3 倍空间, 元素不足 4/9 时减少 1/3 空间.

动态表的势函数

1. $\Phi (\varnothing )=0$;
2. $\forall T\text{ is list},\Phi (T)\ge 0$;
3. 在扩张或收缩前, $\Phi (T)$ 取极大值;
4. 在扩张或收缩完成后, $\Phi (T)$ 取极小值; 插入/删除的开销为 $1$, 扩张/收缩操作的开销为 $T.num$. 发生扩张/收缩时, 势函数的下降抵消了扩张/收缩的开销.

问题 1

元素满时扩大 1 倍空间, 元素不足 1/3 时减少 1/2 空间. 装载比变化：扩张：1 → 1/2；收缩：1/3 → 2/3；范围：$\alpha \in \left[\frac{1}{3},1\right]$.

$$\begin{array}{rl}\Phi (T)& =T.size\times \{\begin{array}{llc}2\left(\frac{1}{2}-\alpha \right)& & \text{if }\alpha <\frac{1}{2},\\ 0& & \text{if }\frac{1}{2}\le \alpha <\frac{2}{3},\\ 3\left(\alpha -\frac{2}{3}\right)& & \text{if }\alpha \ge \frac{2}{3},\end{array}\\ & =\{\begin{array}{llc}T.size-2T.num& & \text{if }\alpha <\frac{1}{2},\\ 0& & \text{if }\frac{1}{2}\le \alpha <\frac{2}{3},\\ 3T.num-2T.size& & \text{if }\alpha \ge \frac{2}{3},\end{array}\end{array}$$

未触发扩张/收缩时, $\Delta \Phi (T)\le 3$, 平摊代价 $\hat{c}=1+\Delta \Phi (T)\le 4$.

触发扩张/收缩时,$\Delta \Phi (T)=-T.num$, 平摊代价 $\hat{c}=1+T.num+\Delta \Phi (T)=1$. 每个操作的平摊代价为 $O(1)$, 总代价为 $O(n)$.

问题 2

$$\Phi (T)=\{\begin{array}{llc}\frac{3}{4}T.size-2T.num& & \text{if }\alpha <\frac{1}{2},\\ 0& & \text{if }\frac{1}{2}\le \alpha <\frac{2}{3},\\ 4T.num-3T.size& & \text{if }\alpha \ge \frac{2}{3},\end{array}$$

未触发扩张/收缩时, $\Delta \Phi (T)\le 4$, 平摊代价 $\hat{c}=1+\Delta \Phi (T)\le 5$.

触发扩张/收缩时,$\Delta \Phi (T)=-T.num$, 平摊代价 $\hat{c}=1+T.num+\Delta \Phi (T)=1$. 每个操作的平摊代价为 $O(1)$, 总代价为 $O(n)$.

伸展树

题目

1. 单旋伸展树的 Splay 操作平摊复杂度不是 $O(\log n)$;

2. 双旋伸展树的 Splay 操作平摊复杂度为 $O(\log n)$.

def splay(x):
    while x.p is not None:
        if x.p.p is None:
            zig(x)
        elif (x.p.l == x) == (x.p.p.l == x.p):
            zig_zig(x)
        else:
            zig_zag(x)

伸展树的势函数

记 $T(x)$ 为以 $x$ 为根的子树. 单个节点的势函数为

$$w(x)=\log |T(X)|$$

总势函数为

$$\Phi (T)=\sum _{x\in T}w(x)$$

$\Phi (T)$ 实际上描述了树的平衡程度, 接近平衡时 $\Phi (T)$ 较小.

zig 操作的平摊分析

对于 zig(x), 记 $x$ 的父节点为 $y$, 旋转后的节点为 $x^{\prime }$ 和 $y^{\prime }$.

$$\begin{array}{rl}\Delta \Phi (T)& =w(x^{\prime })+w(y^{\prime })-w(x)-w(y)\\ & =w(y^{\prime })-w(x)\\ & <w(x^{\prime })-w(x)\end{array}$$

平摊代价 $\hat{c}<w(x^{\prime })-w(x)+O(1)=O(w(x^{\prime })-w(x)+1)$.

单旋伸展树

记 $x$ 在 Splay 到根节点的过程中访问的节点为 $x=x_0,x_1,\dots ,x_h$, 其中 $x_h$ 为根节点, $h$ 为树高.

总的平摊代价为

$$\begin{array}{rl}\hat{c}& <\sum _{i=1}^{h}O(w(x_i)-w(x_{i-1})+1)\\ & =O(x_h)-O(x)+O(h)\\ & =O(h+\log n)\end{array}$$

zig-zig 操作的平摊分析

对于 zig_zig(x), 记 $x$ 的父节点与祖父为 $y$ 和 $z$, 旋转后的节点为 $x^{\prime }$, $y^{\prime }$ 和 $z^{\prime }$.

$$\begin{array}{rl}\Delta \Phi (T)& =w(x^{\prime })+w(y^{\prime })+w(z^{\prime })-w(x)-w(y)-w(z)\\ & =w(y^{\prime })+w(z^{\prime })-w(x)-w(y)\\ & <w(x^{\prime })+w(z^{\prime })-2w(x)\\ & =3(w(x^{\prime })-w(x))+(w(x)+w(z^{\prime })-2w(x^{\prime }))\\ & <3(w(x^{\prime })-w(x))-2\end{array}$$

记 zig_zig(x) 的常数为 $c_1$, 可以调整势函数

$${\Phi }^{\prime }(T)=\frac{c_1}{2}\Phi (T)$$

平摊代价

$$\hat{c}<\frac{c_1}{2}\left(3(w(x^{\prime })-w(x))-2\right)+c_1=O(w(x^{\prime })-w(x))$$

zig-zag 操作的平摊分析

对于 zig_zag(x), 记 $x$ 的父节点与祖父为 $y$ 和 $z$, 旋转后的节点为 $x^{\prime }$, $y^{\prime }$ 和 $z^{\prime }$.

$$\begin{array}{rl}\Delta \Phi (T)& =w(x^{\prime })+w(y^{\prime })+w(z^{\prime })-w(x)-w(y)-w(z)\\ & =w(y^{\prime })+w(z^{\prime })-w(x)-w(y)\\ & <w(y^{\prime })+w(z^{\prime })-2w(x)\\ & =2(w(x^{\prime })-w(x))+(w(y^{\prime })+w(z^{\prime })-2w(x^{\prime }))\\ & <2(w(x^{\prime })-w(x))-2\end{array}$$

记 zig_zag(x) 的常数为 $c_2$, 再次调整势函数

$${\Phi }^{\prime }(T)=\frac{\max \{c_1,c_2\}}{2}\Phi (T)$$

平摊代价

$$\hat{c}<\frac{c_2}{2}\left(2(w(x^{\prime })-w(x))-2\right)+c_2=O(w(x^{\prime })-w(x))$$

双旋伸展树

记 $x$ 在 Splay 到根节点的过程中访问的节点为 $x=x_0,x_1,\dots ,x_k$, 其中 $x_k$ 为根节点.

总的平摊代价为

$$\begin{array}{rl}\hat{c}& <\sum _{i=1}^{h}O(w(x_i)-w(x_{i-1}))+O(1)\\ & =O(x_k)-O(x)+O(1)\\ & =O(\log n)\end{array}$$

并查集

题目

对给定的 $n$ 个元素, 进 xing $m$ 次并查集操作, 证明:

1. 只采用按秩合并的并查集的最差复杂度为 $\Theta (m\log n)$.
2. 采用按秩合并和路径压缩的并查集的平摊复杂度为 $O(m\alpha (n))$.

def find_set(x):
    if x != x.parent:
        # return find_set(x.parent)
        x.parent = find_set(x.parent)
    return x.parent

按秩合并

秩: $x.rank$ 为以 $x$ 为根的树高度的一个上界(如果没有路径压缩, 界是精确的).

def union(x, y):
    x, y = find_set(x), find_set(y)
    if x.rank > y.rank:
        y.parent = x
    else:
        x.parent = y
        if x.rank == y.rank:
            y.rank += 1

引理(秩的性质): $x.rank\le \lfloor \log n\rfloor$.

证明概要: 加强结论为 $x.rank\le \lfloor \log T\rfloor$, 其中 $T$ 为 $x$ 所在的树的大小, 然后使用归纳法.

将大小分别为 $T$ 和 $T^{\prime }$ 的树合并后, 不妨设 $T\ge T^{\prime }$, • 若 $T>T^{\prime }$, 最大秩不超过 $\lfloor \log T\rfloor \le \lfloor \log (T+T^{\prime })\rfloor$; • 若 $T=T^{\prime }$, 最大秩不超过 $\lfloor \log T\rfloor +1=\lfloor \log (T+T^{\prime })\rfloor$.

因此, $x.rank\le \lfloor \log T\rfloor \le \lfloor \log n\rfloor$.

按秩合并的时间复杂度

• find_set: $O(\text{find\_set}(x).rank)=O(\log n)$;

• union: $O(\text{find\_set}(x).rank)+O(\text{find\_set}(y).rank)+O(1)=O(\log n)$

进行 $m$ 次操作的总时间复杂度为 $O(m\log n)$.

最差情况下, 每次合并从叶子节点出发, 且每次合并的两棵树高度相同, 此时复杂度为 $\Omega (m\log n)$.

路径压缩的势函数

定义单个节点的势函数:

$$\phi (x)=\{\begin{array}{ll}0,& \text{if }x.rank=0,\\ \alpha (n)\times x.rank,& \text{if }x\text{ is a root},\\ \varphi (x),& \text{otherwise}\end{array}$$

其中 $\varphi (x)$ 的具体取值留待之后讨论. 需要满足:

• $\phi (x)\le \alpha (n)\times x.rank$, 等号成立当且仅当 $x$ 为根节点或 $x.rank=0$.
• $\varphi (x)$ 只和 $x$ 与 $x$ 的父节点的秩有关, 且对 $x$ 的父节点的秩单调递减.

秩的性质

• $x.rank\le \lfloor \log n\rfloor \le n-1$;
• 按秩合并: $x.rank<x.p.rank$;
• 满足 $x.rank=0$ 的节点均为叶子节点(可能同时也为根节点);
• 节点的秩在并查集操作中不会减少.

推论:

• 路径压缩的过程不会增加节点的势.

union 操作的平摊分析

将 union(x, y) 拆分为三个操作: find_set(x), find_set(y) 和 link(x, y).

对于 link(x, y), 不妨设 $y$ 成为 $x$ 的父节点:

• $x$ 的子节点的势不变;
• $y$ 的子节点的势不增加;
• $x$ 的势减少 ( $\varphi (x)<\alpha (n)\times x.rank$ );
• $y$ 的势增加或不变, 增量不超过 $\alpha (n)$.

平摊代价: $O(\alpha (n))$.

find-set 操作的平摊分析

对于 find_set(x), 记 $x$ 的深度为 $s$, 欲说明 find-set 的平摊代价为 $O(\alpha (n))$, 只需证明在 $x$ 的祖先中有至少 $s-\alpha (n)+O(1)$ 个节点的势减少了, 如此则有:

$$\hat{c}\le s-(s-\alpha (n)+O(1))=O(\alpha (n))$$

引入 $k(x)$, 其值只和 $x$ 及其父节点的秩有关, 且满足 $k(x)<\alpha (n)$, 根据鸽笼原理, 至少有 $s-\alpha (n)-2$ 个节点存在一个祖先节点, 其 $k$ 值与这个节点相同.

根据 $\alpha (n)$ 的定义, $k(x)<\alpha (n)⟺A_{k(x)}(1)\le n-1$.

令 $k(x)=\max \{k:x.p.rank\ge A_k(x.rank)\}$, 满足上述条件.

记 $y$ 是 $x$ 的祖先节点, 且 $k(y)=k(x)$.

路径压缩完成后, $x$ 的父节点变为根节点 $r$, 有

$$r.rank\ge y.p.rank\ge A_k(y.rank)\ge A_k(A_k(x.rank))$$

上式没有对证明起到什么帮助, 但注意到上式最后出现的函数迭代形式. 令 $i(x)=\max \left\{i:x.p.rank\ge A_k^{(i)}(x.rank)\right\}$, 则

$$r.rank\ge A_k(x.p.rank)\ge A_k\left(A_k^{(i)}(x.rank)\right)=A_k^{(i+1)}(x.rank)$$

因此路径压缩使得 $x$ 的 $i(x)$ 增大了.

现在讨论 $\varphi (x)$ 的构造, 需要满足:

• $0\le \varphi (x)<\alpha (n)\times x.rank$.
• $\varphi (x)$ 只和 $x$ 与 $x$ 的父节点的秩有关.
• $\varphi (x)$ 对 $x$ 的父节点的秩单调递减.
• $\varphi (x)$ 对 $i(x)$ 单调递减.

令 $\varphi (x)=(\alpha (x)-k(x))\times x.rank-i(x)$, 则 find-set 的平摊代价为 $O(\alpha (n))$.