算法算法分析

摊销分析：基于统计力学的势函数法

字数统计: 1.3k字   |   阅读时长: 5分
,

摘要: 摊销分析的势函数法初探

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

摊销分析的方法有很多种，最直接的方法是直接计算完成一系列操作的运行时间的上界，这也是前面的文章 可清空表的摊销分析 中使用的方法。这种直接计算的方法在算法导论中称为聚合分析，适用于比较简单的一系列操作，

如果数据结构和操作序列很复杂，则需要一些额外的技术。在实践中比较流行的方法有基于财务模型的记账法，以及基于能量模型的势函数法。在文章 摊销分析：基于财务模型的记账法 中我们讨论了记账法，本文我们讨论势函数法。

案例回顾

考虑一个在数组上维护的线性表，其中元素可用通过下标访问。在这样的线性表上，我们实现一个可清空表，支持以下两个操作：

  • add(x)，将元素 x 添加到表的末尾。
  • clear()，移除所有的元素，使其变成空表。

通过摊销分析我们有以下结论，推导过程参考文章 可清空表的摊销分析。

定理

假设一个可清空表 $S$ 用数组实现，那么在空的可清空表上的 n 个操作需要 $O(n)$ 的时间复杂度。

在前面两篇文章中我们分别用聚合分析法、记账法证明了以上定理，并依次给出了上述可清空表的摊销分析。下面我们还是以此为例，讨论势函数法。

势函数法

势函数法借鉴了统计力学中的能量模型。给数据结构关联一个系统当前势能状态值 $\Phi$。每个操作给 $\Phi$ 贡献一定的势能，即该操作的摊销时间，同时也从 $\Phi$ 中消耗与其实际运行时间成正比的势能。

设 $\Phi_{0} \geq 0$ 表示 $\Phi$ 的初始值，即执行任何操作前的值，记 $\Phi_{i}$ 表示势函数 $\Phi$ 完成第 $i$ 个操作后的值。

使用表示系统势能的势函数法，其核心思想是：用第 $i$ 个操作后的势能变化 $\Phi_{i} - \Phi_{i-1}$ 来描述该操作的摊销时间。

考虑第 $i$ 个操作的作用，令 $t_{i}$ 表示实际运行时间，则可以定义地 $i$ 个操作的摊销运行时间为：

其含义是第 $i$ 个操作的摊销时间是实际时间加上完成该操作引起的势能净增加量（可能是正的，也可能是负的），变形一下，写成以下形式：

其含义是实际时间是摊销时间加上势能的净下降。

记 $T’$ 表示在数据结构上完成 $n$ 个操作的总摊销时间，即：

那么完成 $n$ 个操作的实际运行时间 $T$ 就是：

从这里就可以看出来，只要 $\Phi_{n} \geq \Phi_{0}$，就有 $T \leq T’$，即实际运行时间不超过摊销运行时间。

回到可清空表的例子，我们来看一下势函数法是如何进行的。

选择可清空表中元素实际数目作为系统的势能$\Phi$，此时考虑第 $i$ 个操作，有两种可能的的方法：

  • add(x)：在表中插入元素 x，使得势能 $\Phi$ 增加 1，即 $\Phi_{i} - \Phi_{i-1} = 1$，且实际运行时间是 1 个时间单位，即 $t_{i} = 1$，因此有：

得到 $t_{i}’ = 2$，也就是 $O(1)$。

  • clear()：清除所有 $m$ 个元素最多需要 $t_{i} = m+O(1)$ 个时间单位，其中 $m$ 个时间单位清除，最多 $O(1)$ 个时间单位用于方法调用和额外开销。但这种操作也是系统的势能 $\Phi$ 从 $m$ 降为 $0$，即 $\Phi_{i} - \Phi_{i-1} = -m$，因此有：

得到 $t_{i}’ = O(1)$。

综上，可清空表上执行任何操作的摊销时间均为 $O(1)$。另一方面，由于对 $\forall i \geq 1$，有 $\Phi_{i} \geq \Phi_{0}$，因此在空的可清空表上完成 $n$ 个操作的总时间为 $O(n)$。

总结

使用势函数法的过程中，我们对每个操作分析两个方面，一个是实际时间，这个相当于记账法中实际需要支付的金额；另一个是势能的变化，这个相当于记账法中存入银行或从银行取用的金额。

难点在于精巧地设计势函数的定义，使得数据结构支持的各个操作都能比较容易地分析清楚势能如何变化。在复杂数据结构中，这点并不容易。

Share