资讯

历史

科技

环境与自然

成长

游戏

财经

文学与艺术

美食

健康

家居

文化

情感

汽车

三农

军事

旅行

运动

教育

生活

星座命理

势能分析法

创作时间:

作者:

@小白创作中心

势能分析法

引用

来源

https://www.cnblogs.com/binbin200811/p/18725298

势能分析法

势能分析通过定义一个势能函数（通常表示为
(\Phi))，度量数据结构的潜在能量，即系统状态中的预留资源，这些资源可以用来支付未来的高成本操作。势能的变化用于平衡操作序列的总成本，从而确保整个算法的均摊成本在合理范围内。
——摘自 OI-wiki

原理

定义状态(S)为某一时刻数据结构的状态，初始状态为(S_0)。

其次，定义的势能函数(\Phi(S))需要满足以下两个性质：

初始势能：(\Phi(S_0)=0)。
非负性：任意状态下(\Phi(S)\geq 0)。

Ps：也有说法表示不必满足以上性质，势能函数反映数据结构变化量即可。

对于每个操作，均摊成本(\hat c)定义为

[\hat c=c+\Phi(S_i)-\Phi(S_{i-1}) ]

其中(c)为这次操作所需的实际复杂度。

该公式表明均摊成本等于实际成本加势能变化量。

有一种理解方式是：当(c)小时，势能增加(\Phi(S_i)>\Phi(S_{i-1}))；当(c)大时，势能减小(\Phi(S_i)<\Phi(S_{i-1}))。

我们通过势能函数来分析一系列操作的总成本。

[\sum_{i=1}^n c_i=\sum_{i=1}^n\hat{c_i} -\Phi(S_n)+\Phi(S_0) ]

例题：动态数组的扩容分析

题面

初始时数组大小为(0)，第一次加入数组大小会变为(1)。之后每次加入时，如果数组大小不够，会新开一个大小为原来两倍的数组，在新数组中依次插入原来的数据与当前插入的数。

若不计开新数组的时间，单次插入(O(1))，分析插入(n)个数时的复杂度。

分析

设数组长度为(m)，插入的数的个数为(n)，设势能函数(\Phi_i=2n-m)。

插入操作（不扩容）

操作成本：(c=1)。

势能变化：(n_i=(n_{i-1}+1),m_i=m_{i-1})，(\Phi_i-\Phi_{i-1}=(2\cdot n_i+m_i)-(2\cdot n_{i-1}+m_{i-1})=2)。

均摊成本：(\hat c=c+\Phi_i-\Phi_{i-1}=2)。

插入操作（扩容）

操作成本：(c=n+1)。

势能变化：(n_i=(n_{i-1}+1),m_i=2\cdot m_{i-1}=2\cdot n_{i-1})，(\Phi_i-\Phi_{i-1}=(2\cdot n_i+m_i)-(2\cdot n_{i-1}+m_{i-1})=2-n)。

均摊成本：(\hat c=c+\Phi_i-\Phi_{i-1}=3)。

此处看出虽然扩容操作成本高，但势能变化量减小；反之同理。整体均摊在(O(1))级别。

实践：分析 Splay 树的复杂度

(x)表示节点(x)，(|x|)表示(x)的子树大小。

定义(\Phi(S)=\sum_{i\in S} \log |x|)，证明旋转到根的操作是(\log n)。

(zig-zig)与(zag-zag)。

势能变化量为

[\Phi_i-\Phi_{i-1}=\phi_i(x)+\phi_i(y)+\phi_i(z)-\phi_{i-1}(x)-\phi_{i-1}(y)-\phi_{i-1}(z) ]

由于(\phi_i(x)=phi_{i-1}(z))，所以有

[\begin{align} \Phi_i-\Phi_{i-1}&=\phi_i(x)+\phi_i(y)+\phi_i(z)-\phi_{i-1}(x)-\phi_{i-1}(y)-\phi_{i-1}(z)\ &=\phi_i(y)+\phi_i(z)-\phi_{i-1}(x)-\phi_{i-1}(y) \end{align} ]

根据子树大小关系推导的(\phi)关系，可知

[\begin{align} \Phi_i-\Phi_{i-1}&=\phi_i(y)+\phi_i(z)-\phi_{i-1}(x)-\phi_{i-1}(y)\ &\leq \phi_i(x)+\phi_i(z)-2\cdot \phi_{i-1}(x) \end{align} ]

观察上面的树，不难发现有

[|x'|\geq |x|+|z'| ]

于是我们可以得到（注意与上面的式子不同）

[\begin{align} &\phi_{i-1}(x)+\phi_{i}(z)-2\cdot \phi_i(x)\ &=\log \frac{|x||z'|}{|x'|^2}\leq \log \frac{|x||z'|}{(|x|+|z'|)^2}\ &\leq \frac{|x||z'|}{2|x||z'|}=\log \frac{1}{2}=-1 \end{align} ]

于是均摊势能为

[\begin{align} \hat{c_i}=c_i+\Phi_i-\Phi_{i-1}&\leq 1+3\cdot (\phi_i(x)-\phi_{i-1}(x-1))+(\phi_{i-1}(x)+\phi_i(z)-2\cdot \phi_i(x))\ &=1+3\cdot (\phi_i(x)-\phi_{i-1}(x-1))-1\ &=3\cdot (\phi_i(x)-\phi_{i-1}(x-1)) \end{align} ]

(zig-zag)或(zag-zig)。

首先还是分析势能变化量

[\begin{align} \Phi_i-\Phi_{i-1}&=\phi_i(x)+\phi_i(y)+\phi_i(z)-\phi_{i-1}(x)-\phi_{i-1}(y)-\phi_{i-1} (z)\ &=\phi_i(y)+\phi_i(z)-\phi_{i-1}(x)-\phi_{i-1}(y) \end{align} ]

观察上图，可得

[|x'|\geq |y'|+|z'| ]

同理可得

[\phi_i(y)+\phi_i(z)-2\cdot \phi_i(x)\leq -1 ]

于是有

[\begin{align} \hat c_i&=c_i+\Phi_i-\Phi_{i-1}\ &\leq \phi_i(y)+\phi_i(z)-\phi_{i-1}(x)-\phi_{i-1}(y)-(\phi_i(y)+\phi_i(z)-2\cdot \phi_i(x))\ &=2\cdot \phi_i(x)-\phi_{i-1}(x)-\phi_{i-1}(y)\ &\leq 2\cdot (\phi_i(x)-\phi_{i-1}(x)) \end{align} ]

(zig)或(zag)

[\hat c_i=c_i+\Phi_i-\Phi_{i-1}=1+\phi_i(x)-\phi_{i-1}(x) ]

综上，1.2. 两种操作均摊为(O(\phi_i(x)-\phi_{i-1}(x)))，3 的均摊代价是(O(1+\phi_i(x)-\phi_{i-1}(x)))，一次

splay

是若干次 1.2. 操作与一次 3. 操作的结合，所以一次

splay

的代价为(O(1+\phi_i(x)-\phi_0(x))\leq O(1+\log n)=O(\log n))。

由于其他操作都是基于

splay

，在势能函数中以常数的形式体现，于是我们可以估计一棵 Splay 树的平均复杂度是(O(\log n))的，现在我们来计算一下

[\sum_{i=1}^n c_i=\sum_{i=1}^n \hat c_i +\Phi_n-\Phi_0 ]

根据上面的分析(\sum_{i=1}^n \hat c_i)的代价为(O(n\log n))。

再根据势能函数的定义，有

[-n\log n\leq \Phi_n-\Phi_0\leq n\log n ]

代入原式

[\begin{align} \sum_{i=1}^n c_i&=\sum_{i=1}^n \hat c_i +\Phi_n-\Phi_0\ &\leq O(m\log n)+n\log n\ &=O((m+n)\log n) \end{align} ]

Q.E.D.

习题

栈问题

一个栈，有以下 3 种操作：

入栈
弹出栈顶元素
在栈顶弹出若干元素

通过均摊分析其复杂度。

二进制加法计算器

有一个二进制加法计算器，在

1111+1

时会改变五个数字的值，修改的数字最多达到(O(\log n))，假设计算器修改一个位置的复杂度是(O(1))的，请证明这种计算器执行

是(O(1))的。

序列 GCD

给出一个有(n)个元素的数列，求他们的最大公约数，采用以下算法：

  
gcd(a,b) = if b==0 return a;
              else return gcd(b,a%b)
          
int main()
   ans = a[1]
   for(int i=2; i<=n; ++i)
       ans = gcd(ans,a[i])

求这个算法的时间复杂度，并给出证明。