势能分析

势能法将数据结构和势能关联起来——对于一个初始化的数据结构 $D_0$ 执行 $n$ 个操作, $c_i$ 为 $n$ 个操作的实际代价, $D_i$ 为 $i$ 此操作之后的数据结构。势函数 $\phi$ 将每个数据结构 $D_i$ 映射到一个实数 $\phi(D_i)$ ,为 $D_i$ 的势。

定义

第 $i$ 个操作的摊还代价用势函数定义为:

意即:每个操作的摊还代价为实际代价加上操作引起的势变化。所以总摊还代价为:

根据 $(1)$ 能得到每个步骤的摊还代价, $(2)$ 能算出总实际代价的上界或下界:$\phi(D_n) - \phi(D_0)$ 正为上,负为下。

实例

对于一个势能分析,选取一个正确的势函数至关重要。

定义 $\phi$ 为当前栈中的数据量。

  • $\operatorname{PUSH}$ 压入一个对象,势差为 $1$ ,实际代价为 $1$ ,摊还代价为 $2$ 。

  • $\operatorname{POP}$ 弹出 $x$ 个对象,势差为 $-x$ ,实际代价为 $x$ ,摊还代价为 $0$ 。

所以每一个操作的摊还代价都是 $O(1)$ ,所以 $n$ 个操作的总代价为上界 $O(n)$ 。

均摊复杂度为 $\frac{O(n)}{n} = O(1)$

$\operatorname{Splay}$

分析栈没有意思,分析一下 $\operatorname{Splay}​$ 。

定义势能 $\phi(u)$ 为 $u$ 在当前树中的子树大小取对数,即:$r(u) = \log s_u$ :

首先:

显然 $\phi \in [0, n \log n]$ ,则:

后者上界已然求出,现在需要求出 $c_i$ 的上界,尝试对 $c_i$ 也进行势能分析。

$\operatorname{Zig}$

即 $u$ 旋转到父亲 $v$ :

$\operatorname{ZigZig}$

即将 $u$ 往上同方向旋转两层至 $w$ :

由于:

所以:

$\operatorname{ZigZag}$

即将 $u$ 往上不同方向旋转两层至 $w​$ :

由于:

所以:

合并分析

那么可以得到以下三种情况的均摊复杂度:

状态 复杂度
单旋 $1 + r’(u) - \phi(u)$
正旋正旋 $3(r’(u) - \phi(u))$
正旋逆旋 $2(r’(u) - \phi(u))$

那么根据 $(1)$ ,均摊复杂度:

$n$ 个节点,$m$ 此操作的总复杂度为:

所以,一般将当前点旋到根以保证复杂度,维持势能函数不变。