动机
向数组中插入一个元素通常代价很小,但偶尔数组已满,必须把所有已有元素复制到更大的存储空间中。因此,单次插入的最坏情形界可以与当前元素个数成线性关系。若把这个最坏代价摊给每一次插入,就会大大高估一长串操作的代价:昂贵的复制之间隔着许多廉价的操作。
摊还分析(amortized analysis)先界定整个操作序列的总代价,再把这个界分配给各个操作。它是关于整个序列的最坏情形陈述,而不是对随机输入取平均。我们分析一个精确定义的只含插入操作的动态数组,并用两种证明得到同一个线性总代价界。
定义
初始时数组为空,容量 。倍增插入的规则如下。
定义 1.12.1
(倍增插入数组)
设插入前元素个数为 、容量为 。若 ,则把新元素写入下一个空闲位置。若 ,则分配容量 ,复制全部 个现有元素,然后写入新元素。代价按每复制一个元素计一个单位,写入新元素计一个单位。在此模型中,分配存储空间本身以及释放旧存储空间的代价视为零;若采用其他模型,则必须另行计入这些代价。对于由 次插入组成的序列,其实际代价是这些单位之和。
定义 1.12.2
(数组状态的势能)
元素个数为 、容量为 的状态,其势能定义为
一次操作的摊还代价等于其实际代价加上势能的变化量。势能是一种记账用的量,并不是实际存储的计算工作量;它的用处在于其变化量在整个序列上会相互抵消(telescope)。
定理
定理 1.12.3
(线性总代价)
对每个整数 ,在倍增规则下, 次插入的总代价至多为 。因此摊还代价每次插入至多为三个单位,尽管单次插入的代价可以是 。
定理 1.12.4
(容量界)
在任意正数 次插入之后,容量满足 。在初始的空状态,容量为一。
证明思路或证明
证明
(线性界的势能证明)
初始时 ,且势能始终非负。若某次插入不需要扩容,则其实际代价为一。 增加一时, 至多改变二,所以其摊还代价至多为三。
若数组已满,则插入前 ,实际代价为 。旧势能为 。倍增并写入之后,,,所以新势能为 。因此摊还代价为 。对所有操作求和时各项相互抵消:总实际代价加上最终势能再减去初始势能,至多为 。由于最终势能非负而初始势能为零,故总实际代价至多为 。
证明透视
为什么这个势能能支付复制
证明有一个设计选择和三个检查。选择是 :它初始为零,每次廉价插入至多上升二,而在数组已满时恰好等于 ,与复制代价中的 相同。扩容时这笔已存储的量被释放,所以摊还代价是 ,而不是 。三个检查分别是:廉价情形(,故费用至多为三)、扩容情形(用到 与 ),以及收尾一步——由 与 ,把抵消后的恒等式变成不等式 。
同一个分析也显示换一种增长规则会在哪里出问题。若已满的数组只由 增至 ,插入后的势能是 ,所以 ,摊还代价变成 。扩容时没有任何量被释放,势能无法支付复制;使势能下降的,正是几何选择 。
证明
(容量不变量)
元素个数从不超过容量。在第一次扩容之前,唯一的正元素个数是一,此时容量为一。从 扩容到 之后,新的元素个数是 ,所以新容量严格小于新元素个数的两倍。其后不扩容的插入只会增大元素个数,因而保持这个严格不等式。对操作次数做归纳即证得结论。
证明
(同一界的聚合证明)
相继各次扩容所复制的元素个数依次为 ,最后一次所对应的容量严格小于最终的正元素个数 。它们的和小于 ; 次新写入再加上 。这同样给出当 时总代价小于 。这个等比级数把每次扩容只计一次,而不是把它的代价摊到每一次操作上。
概念视角代数
以闭式表示的精确总代价
扩容发生在第 次插入,并复制 个元素,其中 满足 。因此复制代价之和为 ,而 时的精确总代价为
当 时为 。由于 ,总代价小于 ,与定理一致。
例题详解
例题 1.12.5
(前四次插入)
第一次插入代价为一,之后元素个数/容量为 。第二次复制一个并写入一个,代价为二,之后为 。第三次复制两个并写入一个,代价为三,之后为 。第四次不扩容,只写入一个,之后为 。总实际代价为 。
例题 1.12.6
(一次代价很大的单个操作)
八次插入之后,容量为八。第九次插入复制八个已有元素并写入一个,所以其实际代价为九。这并不与定理矛盾:定理界定的是全部九次插入的总和,而不是要求每一次插入的实际代价都至多为三。
例题 1.12.7
(一次势能计算)
在对容量为四的已满数组扩容之前,,。插入之后变为 ,。实际代价为五,而摊还代价为 。势能的负变化量抵消了这一次操作实际代价的一部分。
常见错误
反例模式
每次只固定增加一点并不足够
一个看似合理的说法是:只要规则是“数组已满时复制全部元素”,总代价就是线性的。取这样的规则:数组已满时,容量恰好增加一。第二次插入复制一个元素,第三次复制两个,第 次复制 个。当 时,复制代价为 ,再加上十次写入的 ,总代价为 ,已超过 。一般地,仅复制就需要 ,所以总代价是平方级的。这个说法之所以不成立,是因为扩容之间的间隔不是几何增长。修正办法是加上假设:容量每次乘以固定因子 ,如倍增一样。
常见错误
(摊还不等于期望)
倍增规则不含任何随机选择。在该代价模型下,其线性序列界对每一个插入序列都成立。若把这个界称为平均情形的结果,就需要一个概率分布,而定理中并没有这样的分布。
常见错误
(摊还常数代价不等于常数延迟)
这一保证并不意味着每次插入都是常数时间:上面的第九次插入代价为九,而在已有 个元素之后的那次插入代价为 。它也不涵盖删除、缩小,以及为每个新槽位分配并初始化的代价,除非在新的分析中把这些操作纳入。
沿着序列追踪势能
记 为第 次插入的实际代价, 为第 次插入之后的势能,并令 。摊还代价为 。把前 个等式相加,得
所有中间的势能都相互抵消。由于每个 且 ,实际总代价至多为 。证明并不要求势能在每一步都增加:在扩容时势能通常反而下降。它所需要的是抵消恒等式以及对最终势能的一个下界。
对于前四次插入,每次操作之后的势能依次为 。变化量为 ,所以摊还代价为 。它们的和是 ,等于实际总代价 加上最终势能 。最终存储的势能并不是额外的实际收费;它是上界记账与已完成的工作之间的差额。
以积分作为另一种记账证明
也可以让每次插入收取三个积分(credit):一个用于支付它自己的写入,两个存起来。当容量从 增长到 时,复制需要 个积分。在先前一次扩容到容量 之后,在该容量再次变满之前,至少已发生 次插入,其中包括触发先前那次扩容的插入。它们每一次所存的两个积分合起来至少提供 个积分。从容量一开始的第一次扩容由第一次插入所存的两个积分支付。把用不完的积分存起来,可以保持余额非负。
只有在指明积分从何而来并在每次扩容时验证余额之后,这种积分解释才构成证明。说一次廉价操作“为以后的操作付费”只是一种直觉;正是对其间插入次数的计数使之变得精确。势能证明用代数方式编码了同样的大致思想,尽管数值势能不必在每个状态都等于这一特定积分方案的余额。
改变增长因子
倍增只是几何增长的一个例子。设初始容量为一,且每当数组已满时就换成容量 的数组,其中 为固定整数,复制和写入的代价不变。所复制的容量依次为 。若最后一次所复制的容量为 ,则它严格小于最终的正元素个数 。因此它们的和至多为
再加上 次写入,得总代价小于 。这个界对所指定的固定整数增长因子有效;对于非整数因子的舍入规则,则需要它们自己的不变量。
几何增长是以时间换取未使用的容量。从 扩容到 之后,元素个数为 ,所以容量小于元素个数的 倍。在两次扩容之间,元素个数增加而容量保持不变。因此在任意正数 次插入之后 。较大的 会同时改变复制界与存储界;最佳的工程选择可能取决于分配代价、内存限制和工作负载,而这些都不属于此数学模型。
势能的选择与有效性
势能函数并不唯一。所选取的 之所以方便,是因为它在初始空状态下也非负。不同的函数可以用不同的常数证明同一个总代价界。重要的是:对每一个允许的操作,摊还代价不等式都成立;初始值已知;并且最终值具有合适的下界。
常见错误
(以为势能必须非负)
不带最大值的表达式 在初始状态 下等于 ,因此并非非负。抵消恒等式真正需要的是 ,而不是 。对 这仍然成立,因为在任意正数次插入之后 (容量界),所以 。若不作这样的检查就略去一个为负或未经验证的最终势能,便是无效的步骤;在所述的只含插入的模型中,取最大值避免了这种记账上的麻烦。
摊还界对所插入的值是稳健的:两个证明中都没有出现关于这些值分布的任何假设。然而它们依赖于模型。若每次复制的代价超过一个常数,或者分配时要初始化每个槽位,就必须把这些代价计入。例如,对每个新分配的槽位收取常数个单位,仍然得到等比和以及线性的总工作量,但常数三不再原样成立。若复制一个元素本身的代价是可变的,则在没有计入这种可变性的情况下,不得套用单位代价定理。
为什么缩小需要单独的规则
本单元从不移除元素。若加入删除与缩小操作,容量策略可能出现抖动:在容量已满时扩容,而一旦占用量刚好降到一半以下就立即缩小,则交替的插入与删除会反复触发对大数组的复制。常见的补救办法是在增长阈值与缩小阈值之间留出间隙,但其正确性与摊还界需要一个同时针对两种操作而设计的势能。上面的只含插入的势能及证明并不能建立该结果。
空间与时间保证描述的也是不同的资源。容量不等式界定的是每次插入之后所保留的槽位数;摊还证明界定的是所计入的写入与复制的总数。一次扩容可能暂时同时需要旧的和新的存储空间,所以该操作期间的峰值内存取决于分配模型。无论是最终容量界还是单位代价的时间证明,单独都不能确定该峰值。
总结
倍增数组偶尔会复制所有已存储的元素,但这些复制发生在呈指数增长的容量处。无论是几何级数的聚合求和,还是非负势能,都表明插入的总代价是线性的。摊还常数代价与偶尔出现的昂贵单个操作是相容的。
练习
快速检查
(第五次插入的实际代价和新容量各是多少?)
比较插入前的元素个数与容量。
解答 · 答案
在此之前,元素个数和容量都是四。这次插入复制四个并写入一个,代价为五;新容量为八。
快速检查
(在对容量为二的已满数组插入元素之前和之后, 分别是多少?)
把 用于倍增前后的状态。
解答 · 答案
之前,。倍增并插入之后,。
快速检查
(为什么聚合的复制代价级数各项是几何递增的?)
看看每次扩容时容量如何变化。
解答 · 答案
每次扩容都使容量加倍,所以所复制的元素个数依次是二的幂。
快速检查
(该定理是否证明了单次插入具有常数的最坏情形延迟?)
回想例题中的第九次插入。
解答 · 答案
没有。发生扩容的插入会复制当前所有元素,其实际代价可以是线性的。该定理界定的是整个序列的总和。