摊还分析(2)—算法导论(24)

2016年08月31日 17:25

1. 动态表

先来介绍动态表的概念。

在使用数组时，我们通常都是先创建一个大小固定的数组，然后再将数据填充进去。这时难免会遇到创建的数组过小或过大的情况。过小则满足不了存储需求；过大则浪费存储空间。于是我们对普通数组进行包装，创造出一种叫做动态表的数据结构。

本篇博客关注于动态表的扩张和收缩问题，将使用摊还分析证明，**虽然插入和删除操作可能会引起表的扩张和收缩，从而有较高的实际代价，但它们的摊还代价都是$O(1)$**。

需要说明的是，用什么样的数据结构来组织动态表不是固定和重要的，除了以上所说的采用数组的方式，你也可以使用堆、栈或散列表来实现。

2. 表扩张

在介绍表的扩张之前，我们先引入在学习散列表 时接触的概念：装载因子$\alpha$。

非空表T的装载因子$\alpha(T)$定义为表中储存的数据项的数量比上表的规模（槽的数量）。

下面用一小段Java代码给出表的扩张操作：

public class Table<T> {

    private Object[] values;
    private int size; // 表中元素的个数

    public void insert(T value) {
        if (values == null) {
            values = new Object[1];
        }
        if (size == values.length) { // 表的扩张
            Object[] newValues = new Object[size * 2]; // 创建一个容量是之前两倍的数组
            System.arraycopy(values, 0, newValues, 0, values.length); // 拷贝原始数据到新数组
            values = newValues;
        }
        values[size] = value;// 插入新数据
        size++;
    }
}

从代码中我们发现，整个insert操作实际上包含两个"插入"过程，一个是copy原始数据，另一个是插入新数据。我们把每次基本插入操作的代价设定为1，然后用基本插入操作的次数来描述insert操作的运行时间。

下面我们分析对一个空表执行n个insert操作的代价。设第$i$次操作的代价为$c_i$。如果当前表有空间容纳新的插入项，那么$c_i = 1$；如果当前表已填满，则会发生一次扩张，此时需要将旧表里的$i-1$项（因为已经插入了i-1次数据）数据copy到新表里面，还要插入新的数据，因此代价$c_i = i$。一个操作的最坏时间是$O(n)$，因此n次操作总运行时间的上界为$O(n^2)$。

和上一篇中的两个例子一样，这个上界也不是紧确的，因为在执行n个操作中，不可能每次操作都遇到最坏情况，即不是每次都需要扩张表。事实上，只有当$i - 1$为2的幂时，才需要扩张。

采用聚合分析分析该问题：第i个操作的代价是：

$$c_i= \begin{cases} i, &\text{若$i-1$恰为2的幂}\cr 1, &\text{其他} \end{cases}$$

因此n个操作的总代价是：

$$\sum_{i=1}^{n}c_i \leq n + \sum_{j=0}^{⌊\lg n⌋} 2^j < n + 2n = 3n$$

而单一操作的摊还代价最多为3。

我们可以用核算法来更加直观地考虑为什么每次插入一项数据需要付出3个单位的代价。假设表在某次扩张后容量变为$m$，此时表中有$\frac{m}{2}$项数据，它们都没有储存任何信用。在进行下一次插入时，我们付出3个单位的代价，1个单位用来支付本次插入；1个单位存储起来用来支付以后移动该数据时的代价；还有1个单位也存储起来用来支付原始的$\frac{m}{2}$项数据中的某项在下一次移动时的代价。这样，在表下一次扩张时，不需要消费额外的代价来支付移动数据这m项数据的代价。

我们还可以用势能法来分析：定义如下的势函数：$\Theta_i(T) = 2 T.size - T.cap$，它表示第$i$次插入后的势能，$T.size$表示表中数据的项数，$T.cap$表示表的大小。易知，$\Theta_0(T) = 0$；表始终处于等于或超出半满状态，即$T.size \geq T.cap / 2$，因此$\Theta_i(T) \geq \Theta_0(T) = 0$。因此，n个insert操作的总摊还代价给出了总实际代价的上界。

下面分析第i个操作的摊还代价。设$cap_i$为第$i$次操作后表的规模。

1. 若第$i$次操作表没有扩张，一次操作本身的实际代价为1；其引起的势能的变化为2。因此一次操作的摊还代价为3。
2. 若第$i$次操作表发生了扩张，一次操作本身的实际代价为$i$；其引起的势能变化为：$[2i - 2(i-1)] - [2×(i - 1) - (i -1)] = 2 - (i - 1) = 3 - i$。因此一次操作的摊还代价也为3。

综上所述，一次插入操作的摊还代价为$O(1)$。

3. 表收缩

表收缩过程正好与扩张过程相反，这里不在赘述。

4. 表的扩张与收缩

值得注意的是，因为我们在扩张时，通常是将表的规模扩增为原来的2倍，相应地，你可能也认为我们应该在表中元素个数不足规模的一半，即$\alpha<\frac{1}{2}$时，进行表的收缩。遗憾的是，这不是一个好的策略。考虑如下场景，当表在发生一次扩张操作后，我们进行两次删除操作，可以看到，表会在这两次删除操作中的第二次发生收缩；接下来我们再进行两次插入操作，同样，表又会在第二次插入操作时进行扩张。重复上述行为，表会一直进行收缩，扩张。即：删除、删除(收缩)、插入、插入(扩张)、删除、删除(收缩)…这样，对于n个操作，每个操作的摊还代价为$\Theta(n)$。

我们改进一下此策略，允许装载因子$\alpha$小于$\frac{1}{2}$，可以想象，选取$\frac{1}{4}$作为$\alpha$的下界是比较合理的，下面我们用势能法证明这点。

首先是势函数的选取，定义势函数为：

$$\Theta(T)= \begin{cases} 2T.size - T.cap, &\text{若$\alpha(T) \geq 1/2$}\cr T.cap/2 - T.size, &\text{若$\alpha(T) < 1/2$} \end{cases}$$

同样，空表的势为0，；势始终大于0。因此对于n个插入和删除的操作序列，其总摊还代价是总实际代价的上界。

下面我们分析第$i$个操作的摊还代价。分两种情况讨论。在此之前，我们做如下定义：用$c_i$表示第$i$个操作的实际代价，用$c_i'$表示摊还代价。同样，$size_i$表示第$i$次操作后储存的数据项的数量，$cap_i$表示第$i$个操作后表的规模。用$\alpha_i$表示第$i$个操作后的势。

4.1 第$i$个操作是插入操作

$size_i = size_{i-1} + 1$

1. 当$\alpha_{i-1} \geq 1 / 2$：

这种情况与我们在表扩张小节中分析的情况一致，摊还代价$c_i'$至多为3。

2. 当 $\alpha_{i-1} < 1 / 2$且$\alpha_i < 1/2$：

第$i$个操作并不能引起表的扩张，$cap_i = cap_{i-1}$。因此$c_i' = 1 + [(cap_i/2 - size_i) - (cap_{i-1}/2 - size_{i-1}] = 0$。

3. 当$\alpha_{i-1} < 1 / 2$且$\alpha_i\geq1/2$：

第$i$个操作并不能引起表的扩张，$cap_i = cap_{i-1}$。因此$c_i' = 1 + [(2size_i - cap_i) - (cap_{i-1}/2 - size_{i-1})] = 3size_i - cap_i - cap_{i-1} / 2$，又因为$\alpha_{i-1} = (i-1 ) / cap_{i-1}$，因此 $c_i' = 3\alpha_{i-1}cap_{i-1} - 3/2 cap_{i-1} + 3 < 3$。

因此，当第$i$个操作是插入操作时，其摊还代价至多为3。

4.2 第$i$个操作是删除操作

$size_i = size_{i-1} - 1$

1. 当$\alpha_{i-1} \geq 1 / 2$且$\alpha_i > 1/2$：

第$i$个删除操作不会引起表的收缩，$cap_i = cap_{i-1},$。因此$c_i' = 1 + [(2size_i - cap_i) - (2size_{i-1} - cap_{i-1})] = -1$。

2. 当$\alpha_{i-1} \geq 1 / 2$且$\alpha_i < 1/2$：

第$i$个删除操作不会引起表的收缩，$cap_i = cap_{i-1}$。因此$c_i' = 1 + [( cap_i /2 - size_i) - (2size_{i-1} - cap_{i-1})] < 2$。

3. 当$\alpha_{i-1} < 1 / 2$：

第$i$个操作可能引起表的收缩。

① 若没有引起表的收缩。则$c_i' = 1 + [(cap_i / 2 - size_i) - (cap_{i-1}/2 - size_{i-1})] = 2$。

② 若引起表的收缩。则$c_i' = (size_i + 1) + [(cap_i / 2 - size_i) - (cap_{i-1} / 2 - size_{i-1})] = 1$

因此，当第$i$个操作是删除操作时，其摊还代价至多为2。

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