第17章-摊还分析

发表于 | 分类于
字数统计: 5.1k | 阅读时长 ≈ 21

摊还分析

from 算法导论（CLRS）

在摊还分析（amortized analysis）中，我们求数据结构的一个操作序列中所执行的所有操作的平均时间，来评价操作的代价。摊还分析不同于平均情况，它并不涉及概率，它可以保证最坏情况下每个操作的平均性能。

17.1 聚合分析

KEY IDEA：证明对所有 $n$ ，一个 $n$ 个操作序列最坏情况下花费的总时间为 $T(n)$，那么，在最坏情况下，每个操作的平均代价，或摊还代价为：$T(n)/n$。

栈操作

某种栈结构共有三种操作：

  • PUSH(S, x)
  • POP(S)
  • MULTIPOP(S, k): 弹出栈顶的前 k 个元素，如果元素个数小于 k 则全部弹出。

通过聚合分析考虑整个序列的 $n$ 个操作：虽然一个单独的 MULTIPOP 操作代价可能很高，但在一个空栈上执行 $n$ 个 PUSH, POP, MULTIPOP 操作序列，代价至多是 $O(n)$。原因在于：

当一个对象压入栈后，我们至多将其弹出一次。因此，对一个非空的栈，可以执行的 POP 操作的次数（包括MULTIPOP 中调用 POP 的次数）最多与 PUSH 操作的次数相等。因此，对于任意 $n​$ 值，任意一个由 $n​$ 个操作组成的序列，代价最多为 $O(n)​$。每个操作的摊还代价为：$O(1)​$。

二进制计数器递增

$k$ 位二进制计数器递增问题：计数器初值为 0，我们用一个位数组 $A[0 .. k-1]$ 作为计数器。当计数器保存的二进制值为 $x$ 时，$x$ 的最低位保存在 $A[0]$ 中，最高位保存在 $A[k-1]$ 中。具体而言：

1
2
3
4
5
6
7
def INCREMENT(A):
    i = 0
    while i < A.length() and A[i] == 1:
        A[i] = 0
        i = i + 1
    if i < A.length():
    	A[i] = 1

对于 $n$ 个 INCREMENT 操作组成的序列，$A[i]$ 会翻转 $\lfloor n/ 2^i\rfloor$ 次，因此，该序列进行的翻转操作总数为：

因此每个操作的平均代价，即摊还代价为：$O(n)/n = O(1)$。

17.2 核算法

用核算法进行摊还分析时，我们对不同操作赋予不同费用，赋予某些操作的摊还代价可能多于或少于其实际代价。当一个操作的摊还代价超出其实际代价时，我们将差额存入数据结构中的特定对象——信用。对于后续操作中摊还代价小于实际代价的情况，信用可以用来支付差额。信用必须恒大于等于零，因此：如果用 $c_i$ 表示第 $i$ 个操作的实际代价，用 $\hat{c}_i$ 表示其摊还代价，则对任意 $n$ 个操作的序列：

这样，总摊还代价是总实际代价的上界。

栈操作

我们从一个空栈开始，当一个空盘放在一叠盘子最上面时，我们用 1 美元支付压栈操作的实际代价，将 1 美元存为信用（共计 2 美元）。这一美元实际上是作为将来它被弹出栈时代价的预付费。因此当执行一个 POP 或 MULTIPOP 操作时，不需要缴纳任何费用。因此总摊还代价为 $O(n)$，总实际代价也是。

二进制计数器递增

在摊还分析中，对一次置位操作，我们将其摊还代价设为 2 美元。当进行置位时，用 1 美元 支付其实际代价，并用 1 美元预付复位操作的代价。因此任意时刻，计数器中任何为 1 的位都存有 1 美元的信用。

1
2
3
4
5
6
7
def INCREMENT(A):
    i = 0
    while i < A.length() and A[i] == 1:
        A[i] = 0
        i = i + 1
    if i < A.length():
    	A[i] = 1	// 置位操作

每个 INCREMENT 操作至多置位 1 次，因此总摊还代价为 $O(n)$。

1.3 势能法

势能法摊还分析并不将预付代价表示为数据结构中特定对象的信用，而是表示为“势能”，将“势能”释放即可用来支付未来操作的代价，我们将势能与整个数据结构而不是特定对象相关联。

势能法工作如下：

我们将对一个初始数据结构 $D_0$ 执行 $n$ 个操作。对 $i = 1, 2, \dots, n$，令 $c_i$ 为第 $i$ 个操作的实际代价，令 $D_i$ 为在数据结构 $D_{i-1}$ 上执行第 $i$ 次操作得到的结果数据结构。势函数 $ \Phi $ 将每个数据结构 $D_i$ 映射到一个实数 $\Phi(D_i)$，此值即为关联到数据结构 $D_i$ 的势。第 $i$ 个操作的摊还代价 $\hat{c}_i$ 用势函数 $ \Phi $ 定义为:

因此，每个操作的摊还代价等于其实际代价加上此操作引起的势能变化。那么总摊还代价为：

我们通常将 $\Phi(D_0)$ 简单定义为 0，那么只需选择势函数 $\Phi(D_i) \geq 0$，则摊还代价即为实际代价的上界。

栈操作

我们将一个栈的势函数定义为其中对象的数量，则 PUSH 操作的摊还代价为：

MULTIPOP 操作的摊还代价为：

同理，普通的 POP 操作的摊还代价也为 0。

因此 $n$ 个操作的总摊还代价为 $O(n)$ 。

二进制计数器递增

我们将计数器执行 $i$ 次 INCREMENT 操作后的势定义为 $b_i$ —— 第 $i$ 次操作后计数器中 1 的数量。

那么 INCREMENT 操作的摊还代价如下：

假设第 $i$ 个 INCREMENT 操作将 $t_i$ 个位复位，则其实际代价至多为 $t_i + 1$（额外有一个置位）。如果 $b_i = 0$，则第 $i$ 个操作将所有 $k$ 位都复位了，因此 $b_{i-1} = t_i = k$。如果 $b_i > 0$，则 $b_i = b_{i-1} - t_i + 1$。无论哪种情况，$b_i \leq b_{i-1} - t_i + 1$，势差为：

因此，摊还代价为：

所以 $n$ 个 INCREMENT 操作的总实际代价为 $O(n)$。

例题

17.3-6

证明：如何用两个普通的栈实现一个队列，使得每个 ENQUEUE 和 DEQUEUE 操作的摊还代价为 $O(1)$。

解：用核方法进行分析。

ENQUEUE 操作费用为 3 （实际操作 PUSH 为1，剩下两个分别预存为：从 stack 1 到 stack 2 的 POP/PUSH 以及从 stack 2 中 POP）。

DEQUEUE 操作费用为 0

17.3-7

为动态整数多重集 $S$ 设计一种数据结构，支持如下两个操作：

  • INSERT(S,x) ：将 $x$ 插入 $S$ 中。
  • DELETE-LARGE-HALF(S) ：将最大的 $\lceil|S|/2\rceil$ 个元素从 $S$ 中删除。

解释如何实现这种数据结构，使得任意 $m$ 个 INSERT 和 DELETE-LARGE-HALF 操作的序列能在 $O(m)$ 时间内完成。还要实现一个能在 $O(|S|)$ 时间内输出所有元素的操作。

解：我们将数据存在一个数组中。

DELETE-LARGE-HALF(S) 可分为两步实现：

  1. 得到中位数 $m$ （具体算法见第 9 章），时间复杂度为 $O(n)$ 其中 $n$ 为数组中元素个数。
  2. 遍历数组，将值小于等于 $m$ 的元素存入新数组中，时间复杂度为 $O(n)$ 其中 $n$ 为数组中元素个数。

INSERT(S,x) ：操作只需将 $x$ 插入 $S$ 中即可，时间复杂度为 $O(n)$ 其中 $n$ 为数组中元素个数。

因此总的时间复杂度为 $O(n)$ ，$n$ 的最大值为 $m$ ，因此任意 $m$ 个操作能在 $O(m)$ 的时间内完成。

为了输出所有的元素，只需遍历整个数组，时间复杂度为 $O(|S|)$ 。

17.4 动态表

对于某些应用程序，我们可能无法预先知道它会将多少个对象存储在表中，因此，我们为一个表分配一定的空间

  • 原表空间不够时，需要为其重新分配更大的内存空间，并将所有对象从原表中复制到新的内存空间中。
  • 如果从表中删除了许多元素，那么可能为其重新分配一个更小的内存空间就是值得的。

在本节，我们研究表的动态扩张与收缩的问题，通过分析可以证明：

  • 虽然插入和删除操作可能会引起表扩张或收缩，但其摊还代价都是 $O(1)$。
  • 动态表中的空闲空间相对于总空间的比例永远不会超过一个常量分数。

我们首先分析只允许插入数据项的情况，然后考虑既允许插入又允许删除的一般情况。

17.4.1 表扩张

当试图向一个满的表插入一个元素时，我们必须扩张表。由于我们总是需要表位于连续的内存空间，因此必须为更大的新表分配一个新的数组。一种常用的策略是：为新表分配 2 倍于旧表的槽。如果只允许插入操作，那么浪费的空间永远不会超过总空间的一半。

1
2
3
4
5
6
7
8
9
10
11
12
def Table_insert(T, x):
    if T.size() == 0:
        allocate T.table with 1 slot
        T.size = 1
    if T.num == T.size():
        allocate newtable with 2*T.size() slots
        insert all items in T.table into newtable
        free T.table
        T.table = newtable
        T.size() = 2*T.size()
    insert x into T.table
    T.num ++

聚合分析

因此不难看出，上述过程中有两个插入过程。我们设每次基本插入操作的代价为 1，那么在执行 $n$ 个 Table_insert 操作时，第 $i$ 次操作的代价为：

因此 $n$ 个 Table_insert 操作的总代价满足：

因此，单一操作的摊还代价至多为 3 。

核方法

当我们的表从 $m​$ 扩张为 $2m​$ 大小时，我们需要移动 $m​$ 个元素。因此共计要支付 $m​$ 美元。

当我们的表在某次扩张之后大小为 $m$ ，则表中已经存在了 $m/2$ 的元素项，并且表的信用为 $0$。那么我们每插入一个新的元素：立刻发生的插入操作花费 1 美元，预留给自己扩张到 $2m$ 时的费用为 1 美元，为表中已存在的某一元素预留到扩张时的费用为 1 美元。那么到 $m$ 个数据已满时，每个数据项均存储了 1 美元，可以进行扩张。

所以，我们处理每个数据项只需付出 3 次基本插入操作的代价。

势能法

我们定义一个势函数 $\Phi$ ，在表扩张操作之后，其值为 0 。在表满时其值为表的规模，这样就可以利用势能来支付下一次扩张的代价。势能函数定义为：

为了分析第 $i$ 次插入操作之后的摊还代价，我们令 $num_i$ 表示第 $i$ 个操作之后表中数据项的数量，$size_i$ 表示第 $i$ 个操作后表的总规模，$\Phi_i$ 表示第 $i$ 个操作后的势。

如果第 $i​$ 个操作没有触发表扩张：

如果第 $i$ 的操作发生表扩张：

17.4.2 表扩张和收缩

为了实现删除操作，将指定数据项从表中删除是很简单的。但是为了限制浪费的空间，我们可以在装载因子变得太小时对表进行收缩操作：当表中数据项数量下降的太少时，我们分配一个新的更小的表，然后将数据项从旧表复制到新表中。理想情况下，我们希望保持：

  • 动态表的装载因子有一个正的常数下界。
  • 一个表操作的摊还代价有一个常数上界。

我们假定用基本插入、删除操作的次数来衡量动态表操作的代价。

当向一个满表插入一个新的数据项时，我们仍然将表的规模加倍，但只有当装载因子小于 $1/4$ 而不是 $1/2$ 时，我们才将表规模减半。因此，装载因子的下界为 $1/4$ 。

势能法

我们用势能法分析 $n$ 个 TABLE-INSERT 和 TABLE-DELETE 操作组成的序列的代价。

首先定义一个势函数 $\Phi$，在扩张或收缩操作之后其值为 0， 而当装载因子增长到 1 或者降低到 1/4 时，累计足够支付扩张或收缩操作代价的值。定义势函数如下：

观察到空表的势为 0，且势函数不可能为负，所以用势函数定义的操作序列的总摊还代价是总实际代价的上界。

为了分析第 $n$ 次 TABLE-INSERT 和 TABLE-DELETE 操作之后的摊还代价，我们令 $num_i$ 表示第 $i$ 个操作之后表中数据项的数量，$size_i$ 表示第 $i$ 个操作后表的总规模，$\Phi_i$ 表示第 $i$ 个操作后的势，$\alpha_i$ 表示第 $i$ 个操作后的装载因子。

首先分析第 $i​$ 个操作为 TABLE-INSERT 的情况。若 $\alpha_{i-1} \geq 1/2​$，分析与上节类似，不管表扩张与否，操作的摊还代价至多为 3。若 $\alpha_{i-1} < 1/2​$ ，则第 $i​$ 个操作并不能令表扩张，则第 $i​$ 个操作的摊还代价为：

若 $\alpha_{i-1} < 1/2$ 但 $\alpha_{i} \geq 1/2$，则：

因此，一个插入操作的摊还代价至多为 3。

我们现在来分析第 $i$ 个操作是 TABLE-DELETE 的情况。若 $\alpha_{i-1} < 1/2$，需要考虑删除操作实都引起表收缩，如果未引起表收缩，那么

而如果引发了表收缩操作，则操作的实际代价为 $c_i = num_i + 1$，因为我们删除了一个数据项，又移动了 $num_i$ 个数据项。我们知道 $size_i/2 = size_{i-1}/4 = num_{i-1} = num_i + 1$，那么

而当第 $i​$ 个操作是 TABLE-DELETE ，且 $\alpha_{i-1} \geq 1/2​$ 时，如果 $\alpha_{i} \geq 1/2​$，那么不引起收缩操作，

如果 $\alpha_{i} < 1/2$ 并且 $\alpha_{i} \geq 1/4$ 时，

总之，由于每个操作的摊还代价上界是一个常数，在一个动态表上执行任意 $n$ 个操作的实际运行时间为 $O(n)$。

习题

17.4-3

Suppose that instead of contracting a table by halving its size when its load factor drops below $1 / 4$, we contract it by multiplying its size by $2/3$ when its load factor drops below $1/3$. Using the potential function

show that the amortized cost of a TABLE-DELETE that uses this strategy is bounded above by a constant.

  • $\alpha_i > 1/2$
  • $1/3 < \alpha_i \leq 1/2​$

如果第 $i$ 次删除操作引起表收缩：

那么

17-2 动态二分查找

Binary search of a sorted array takes logarithmic search time, but the time to insert a new element is linear in the size of the array. We can improve the time for insertion by keeping several sorted arrays.

Specifically, suppose that we wish to support $\text{SEARCH}​$ and $\text{INSERT}​$ on a set of $n​$ elements. Let $k = \lceil \lg(n + 1) \rceil​$, and let the binary representation of $n​$ be $\langle n_{k - 1}, n_{k - 2}, \ldots, n_0 \rangle​$. We have $k​$ sorted arrays $A_0, A_1, \ldots, A_{k - 1}​$, where for $i = 0, 1, \ldots, k - 1​$, the length of array $A_i​$ is $2^i​$. Each array is either full or empty, depending on whether $n_i = 1​$ or $n_i = 0​$, respectively. The total number of elements held in all $k​$ arrays is therefore $\sum_{i = 0}^{k - 1} n_i 2^i = n​$. Although each individual array is sorted, elements in different arrays bear no particular relationship to each other.

a. Describe how to perform the $\text{SEARCH}$ operation for this data structure. Analyze its worst-case running time.

b. Describe how to perform the $\text{INSERT}$ operation. Analyze its worst-case and amortized running times.

c. Discuss how to implement $\text{DELETE}$.

a. 搜索操作可以通过搜索每个单独排好序的数组来实现。由于每个数组已经排好序，那么搜索一个数组的时间开销为 $O(\lg m )​$ 其中 $m​$ 为数组的大小。在最坏情况下，我们可以假设

$A_0, A_1, \ldots, A_{k - 1}​$ 都是满的，其中 $k=\lceil\lg (n+1)\rceil​$，一次不成功查询花费的总时间为：

因此，最坏情况下的运行时间为：$\Theta\left(\lg ^{2} n\right)$。

b. 我们创建一个大小为 1 的数组，其中包含要插入的新元素。如果 $A_0$ 为空，那么我们将 $A_0$ 替换为新构造的数组。否则，我们对两个数组进行归并，依次进行下去。归并两个大小为 $m$ 的有序数组时间为 $2m$。那么，

最坏情况下，我们假设$A_0, A_1, \ldots, A_{k - 2}$ 都是满的，则：

因此，最坏情况下运行时间为：$\Theta(n)​$。

我们可以利用核算法分析摊还代价。每次插入操作我们支付 $k $ 美元，其中 $k=\lceil\lg (n+1)\rceil$。其中 1 美元用于实际的插入开销，而 $k-1$ 美元预留为归并时使用。每次合并后，它都会移动到索引更高的数组，例如从 $A_i$ 移动至 $A_{i-1}$ 中。每个元素至多会移动 $k-1$ 次，因此预留的 $k-1$ 美元可以支付每一次元素移动。那么我们每次插入的摊还代价即为：$\Theta(\lg n)$。

c.

DELETE(x) 操作实现如下：

  1. 寻找到满足 $A_j​$ 数组为满的最小 $j​$。令 $y​$ 为 $A_j​$ 的最后一个元素。
  2. 利用 SEARCH(x) 操作找到 $x$ 所在的数组 $A_i$。
  3. 将 $x$ 从 $A_i$ 中移除，并将 $y$ 置于 $A_i $ 中。之后将 $y$ 移动到其在 $A_i$ 中的正确位置。
  4. 将 $A_j$ 拆分：第 1 个元素置于 $A_0$ 中，接着两个元素置于 $A_1$ 中，接着四个元素置于 $A_2$ 中，依次类推直到 $A_j$ 为空。