Algorithm 版 (精华区)

发信人: Lerry (想不开·撞树), 信区: Algorithm
标  题: 动态表
发信站: 哈工大紫丁香 (2002年03月22日14:49:42 星期五), 站内信件

动态表
在有些应用中，在开始的时候无法预知在表中要存储多少个对象。可以先为该表分配一
定的空间，但后来可能会觉得不够，这样就要为该表分配一个更大的空间，而表中的对
象就复制到新表中。类似地，如果有许多对象被从表中删去了，就应该给原表分配一个
更小的空间。在后文中，我们要研究表的动态扩张和收缩的问题。利用平摊分析，我们
要证明插入和删除操作的平摊代价为O(1)，即使当它们引起了表的扩张和收缩时具有较
大的实际代价也时一样的。此外，我们将看到如何来保证某一动态表中未用的空间始终
不超过整个空间的一部分。
假设动态表支持Insert和Delete操作。Insert将某一元素插入表中，该元素占据一个槽
（即一个元素占据的空间）。同样地，Delete将一个元素从表中去掉，从而释放了一个
槽。用来构造这种表的数据结构方法的细节不重要，可以选用的有栈，堆或杂凑表结构
。我们将用一个数组或一组数组来实现对象存储。
大家将会发现在采用了杂凑表中分析杂凑技术时引入的装载因子概念后会很方便。定义
一个非空表T的装载因子a(T)为表中存储的对象项数和表的大小(槽的个数)的比值。对一
个空表（其中没有元素）定义其大小为0，其装载因子为1。如果某一动态表的装载因子
以一个常数为上界，则表中未使用的空间就始终不会超过整个空间的一常数部分。
我们先开始分析只对之做插入的动态表，然后再考虑既允许插入又允许删除的更一般的
情况。
表的扩张
假设一个表的存储空间分配为一个槽的数组，当所有的槽都被占用的时候这个表就被填
满了，这时候其装载因子为1。在某些软件环境中，如果试图向一个满的表中插入一个项
，就只会导致错误。此处假设我们的软件环境提供了存储管理系统，它能够根据请求来
分配或释放存储块。这样，当向一满的表中插入一个项时，我们就能对原表进行扩张，
即分配一个包含比原表更多槽的新表，再将原表中各项数据复制到新表中去。
一种常用的启发技术是分配一个比原表大一倍的新表。如果只对表进行插入操作，则表
的装载因子总是至少为1/2，这样浪费掉的空间就始终不会超过表的总空间的一半。
在下面的伪代码中，我们假设对象T表示一个表，域table[T]包含了一个指向表的存储块
的指针，域num[T]包含了表中的项数，域size[T]为表中总的槽数。开始时，表是空的：
num[T]=size[T]=0
Insert(T, x)
1  if size[T]=0
2    then 给table[T]分配一个槽的空间
3         size[T]←1
4  if num[T]=size[T]
5    then 分配一个有2*size[T]个槽的空间的新表
6         将table[T]中所有的项插入到新表中
7         释放Table[T]
8         table[T]指向新表的存储块地址
9         size[T]←2*size[T]
10 将x插入table[T]
11 num[T]←num[T]+1
请注意，这里有两种“插入”过程：Insert过程本身与第6行和第l0行中的基本插入。可
以根据基本插入的操作数来分析Insert的运行时间，每个基本插入操作的代价为1。假淀
Insert的实际运行时间与插入项的时间成线性关系，使得在第2行中分配初始表的开销为
常数，而第5行与第7行中分配和释放存储的开销由第6行中转移表中所有项的开销决定。
我们称第5-9行中执行then语句的事件为一次扩张。
现在我们来分析一下作用于一个初始为空的表上的n次Insert操作的序列。设第i次操作
的代价ci，如果在当前的表中还有空间（或该操作是第一个操作），则ci=1，因为这时
我们只需在第10行中执行一次基本插入操作即可。如果当前的表是满的，则发生一次扩
张，这时ci=i；第10行中基本插入操作的代价1再加上第6行中将原表中的项夏制到新表
中的代价i-1。如果执行了n次操作，则一次操作的最坏情况代价为O(n)，由此可得n次操
作的总的运行时间的上界O(n)。
但这个界不很紧确，因为在执行n次Insert操作的过程中并不常常包括扩张表的代价。特
别地，仅当i-1为2的整数幕时第i次操作才会引起一次表的扩张。实际上，每一次操作的
平摊代价为O(1)，这一点我们可以用聚集方法加以证明。第i次操作的代价为
由此，n次Insert操作的总代价为
因为至多有  次操作的代价为1，而余下的操作的代价就构成了一个几何级数。因为n次
Insert操作的总代价为3n，故每次操作的平摊代价为3。
通过采用会计方法，我们可以对为什么一次Insert操作的平摊代价会是3有一些认识。从
直觉上看，每一项要支付三次基本插入操作：将其自身插入现行表中，当表扩张时对其
自身的移动，以及对另一个在扩张表时已经移动过的另一项的移动。例如，假设刚刚完
成扩张后某一表的大小为m，那么表中共有m/2项，且没有“存款”。对每一次插入操作
要收费3元。立即发生的基本插入的代价为1元，另有1元放在刚插入的元素上作为存款，
余下的1元放在已在表中的m/2个项上的某一项上作为存款。填满该表另需要m/2次插入，
这样，到该表包含了m个项时，该表已满，每一项上都有1元钱以支付在表扩张期间的插
入。
也可以用势能方法来分析一系列n个Insert操作，我们还将在后文中用此方法来设计一个
平摊代价为O(1)的Delete的操作。开始时我们先定义一个势函数F，在完成扩张时它为0
，当表满时它也达到表的大小，这样下一次扩张的代价就可由存储的势来支付了。函数

        (4)
是一种可能的选择。在刚刚完成一次扩张后，我们有num[T]=size[T]/2，于是有F(T)=0
，这正是所希望的。在就要做一次扩张前，有num[T]=size[T]，于是F(T)=num[T]，这也
正是我们希望的。势的初值为0，又因为表总是至少为半满，num[T]≧size[T]/2，这就
意味着F(T)总是非负的。所以，n次Insert操作的总的平摊代价就是总的实际代价的一个
上界。
为了分析第i次Insert操作的平摊代价，我们用numi来表示在第i次操作后表中所存放的
项数，用sizei表示在第i次操作之后表的大小，Fi表示第i次操作之后的势。开始时，n
um0=O，size0=0和F0=0。
如果第i次Insert操作没有能触发一次表的扩张，则numi=numi-1+1，sizei=sizei-1，且
该操作的平摊代价为
如果第i次操作确实触发了一次扩张，则numi=numi-1+1，sizei = 2sizei-1 = 2numi-1
=2(numi -1)，且该操作的平摊代价为
图3画出了numi，sizei和Fi的各个值。在第i次操作后对这些量中的每一个都要加以计算
。图中红线表示numi，紫线表示sizei，蓝线表示Fi。注意在每一次扩张前，势已增长到
等于表中的项目数，因而可以支付将所有元素移到新表中去的代价。此后，势降为0，但
一但引起扩张的项目被插入时其值就立即增加2。
图3 对表中项目数numi，表中的空位数sizei，以及势Fi作用n次Insert操作的效果
表扩张和收缩
为了实现Delete操作，只要将指定的项从表中去掉即可。但是，当某一表的装载因子过
小时，我们就希望对表进行收缩，使得浪费的空间不致太大。表收缩与表扩张是类似的
：当表中的项数降得过低时，我们就要分配一个新的、更小的表，而后将旧表的各项复
制到新表中。旧表所占用的存储空间则可被释放，归还到存储管理系统中去。在理想情
况下，我们希望下面两个性质成立：
动态表的装载因子由一常数作为下界；
各表操作的平摊代价由一常数作为下界。
另外，我们假设用基本插入和删除操作来测度代价。
关于表收缩和扩张的一个自然的策略是当向表中插入一个项时将表的规模扩大一倍，而
当从表中删除一项就导致表的状态小干半满时，则将表缩小一半。这个策略保证了表的
装载因子始终不会低于1/2，但不幸的是，这样又会导致各表操作具有较大的平摊代价。
请考虑一下下面这种情况：我们对某一表T执行n次操作，此处n为2的整数幂。前n/2个操
作是插入，由前面的分析可知其总代价为O(n)。在这一系列插入操作的结束处，num[T]
=size[T]=n/2。对后面的n/2个操作，我们执行下面这样一个序列：I,D,D,I,I,D,D,I,I
，……，其中I表示插入，D表示删除。第一次插入导致表扩张至规模n。紧接的两次删除
又将表的大小收缩至n/2；紧接的两次插入又导致表的另一次扩张，等等。每次扩张和收
缩的代价为Θ(n)，共有Θ(n)次扩张或收缩。这样，n次操作的总代价为Θ(n2)，而每一
次操作的平摊代价为Θ(n)。
这种策略的困难性是显而易见的：在一次扩张之后，我们没有做足够的删除来支付一次
收缩的代价。类似地，在一次收缩后，我们也没有做足够的插入以支付一次扩张的代价
。
我们可以对这个策略加以改进，即允许装载因子低于1/2。具体来说，当向满的表中插入
一项时，还是将表扩大一倍，但当删除一项而引起表不足1/4满时，我们就将表缩小为原
来的一半。这样，表的装载因子就以常数1/4为下限界。这种做法的基本思想是使扩张以
后表的装载因子为1/2。因而，在发生一次收缩前要删除表中一半的项，因为只有当装载
因子低于1/4时方会发生收缩。同理，在收缩之后，表的装载因子也是1/2。这样，在发
生扩张前要通过扩张将表中的项数增加一倍，因为只有当表的装载因子超过1时方能发生
扩张。
我们略去了Delete的代码，因为它与Insert的代码是类似的。为了方便分析，我们假定
如果表中的项数降至0，就释放该表所占存储空间。亦即，如果num[T]=0，则size[T]=0
。
现在我们用势能方法来分析由n个Insert和Delete操作构成的序列的代价。先完义一个势
函数F，它在刚完成一次扩张或收缩时值为0，并随着装载因子增至1或降至1/4而变化。
我们用a(T)= num[T]/size[T]来表示一个非空表T的装载因子。对一个空表，因为有num
[T]=size[T]=0，且a(T)=1，故总有num[T]=a(T)*size[T]，无论该表是否为空。我们采
用的势函数为
            (5)
请注意，空表的势为0；势总是非负的。这样，以F表示的一列操作的总平摊代价即为其
实际代价的--个上界。
在进行详细分析之前，我们先来看看势函数的某些性质。当装载因子为1/2时，势为0。
当它为1时，有size[T]=num[T]，这就意味着F(T)=num[T]，这样当因插入一项而引起一
次扩张时，就可用势来支付其代价。当装载因子为1/4时，我们有size[T]=4*num[T]，它
意味着F(T)=num[T]，因而当删除某个项引起一次收缩时就可用势来支付其代价。图4说
明了对一系列操作势是如何变化的。
图4 对表中的项目数numi、表中的空位数sizei及势Fi
作用由n个Insert和Delete操作构成的操作序列的效果
图4中红线表示numi，紫线表示sizei，蓝线表示Fi。注意在每一次扩张前，势已增长到
等于表中的项目数，因而可以支付将所有元素移到新表中去的代价。类似地，在一次收
缩之前，势也增加到等于表中的项目数。
为分析n个Insert和Delete的操作序列，我们用 来表示第i次操作的实际代价，ci表示其
参照F的平摊代价，numi表示在第i次操作之后表中存储的项数，sizei表示第i次操作后
表的大小，ai表示第i次操作后表的装载因子，Fi表示第i次操作后的势。开始时，num0
=O，size0=0，a0=1，F0=0。
我们从第i次操作是Insert的情况开始分析。如果ai-1≥1/2，则所要做的分析就与对表
扩张的分析完全一样。无论表是否进行了扩张，该操作的平摊代价ci都至多是3。如果a
i-1<1/2，则表不会因该操作而扩张，因为仅当ai-1=1时才发生扩张。如果还有ai<1/2，
则第i个操作的平摊代价为
如果ai-1< 1/2，但ai≥1/2，那么
因此，一次Insert操作的平摊代价至多为3。
现在我们再来分析一下第i个操作是Delete的情形。这时，numi=numi-1-1。如果ai-1< 
1/2，我们就要考虑该操作是否会引起一次收缩。如果没有，则sizei=sizei-1，而该操
作的平摊代价则为
如果ai-1< 1/2且第i个操作触发一次收缩，则该操作的实际代价为ci=numi+1，因为我们
删除了一项，移动了numi项。这时，sizei/2 = sizei-1/4 = numi+1，而该操作的平摊
代价为
当第i次操作为Delete且ai-1≥1/2时，其平摊代价仍有一常数上界。具体的分析从略。

总之，因为每个操作的平摊代价都有一常数上界，所以作用于一动态表上的n个操作的实
际时间为O(n)。

--
　　不在乎天长地久，就怕你从来没有！

※ 来源:·哈工大紫丁香 bbs.hit.edu.cn·[FROM: 天外飞仙]