摊还分析是一种分析算法或数据结构在一系列操作中所消耗资源的方法。它不是孤立地约束每次操作的成本,而是约束整个序列的总成本,再将其分摊到各次操作上。某次操作的成本可能很高,但摊还成本仍然可以很低,因为高成本操作之间必须有足够多的低成本操作,不可能频繁出现。与平均情况分析不同,摊还分析不需要假定输入的概率分布。
定义与适用范围
设一个包含 次操作的序列中,各次操作的实际成本为 。其总成本为
摊还界为分析所涵盖的、从指定初始状态出发的每个合法序列,确立总成本的上界。如果所有这样的序列,其成本都不超过 ,其中 为常数,那么这些操作就具有常数摊还成本。
更一般地,分析可以为每次操作指定一个摊还费用 ,使得
不同类型的操作可以具有不同的费用。例如,插入操作的摊还成本可以是常数,而删除操作的摊还成本可以是对数级。
摊还分析最常用于分析时间复杂度,但同样的推理也可以用来约束其他可累加的成本,例如内存传输、磁盘访问或单个比特的翻转次数。有效的分析必须明确其成本模型:例如,如果元素本身的大小可变,复制一个元素就不一定是常数时间操作。
与最坏情况分析和平均情况分析的关系
必须区分以下三种保证:
- 单次操作的最坏情况成本约束每次操作的成本,包括成本最高的那次操作。
- 平均情况成本根据明确或隐含指定的输入分布取平均。
- 摊还成本约束任意合法序列的总成本,允许单次操作的实际成本超过为其指定的费用。
因此,摊还分析是一种针对操作序列的最坏情况分析,并不是声称不利输入出现的概率很小。它利用的是高成本操作在组合方式上受到的限制。
可调整容量的数组可以说明这种区别。触发扩容的追加操作可能需要线性时间,但一系列追加操作的总时间仍然可以是线性的。因此,追加操作具有常数摊还成本,却不具有常数最坏情况成本。
摊还与随机化是相互独立的思想。随机化算法可以具有期望摊还界,将针对操作序列的论证与对随机选择求期望值结合起来。这种保证不应与确定性的摊还界混淆。
主要方法
三种标准方法——聚合分析法、记账法和势能法——以不同方式建立操作序列层面的界。它们往往表达的是同一个底层论证。
聚合分析法
聚合分析法直接约束一个序列执行的工作总量,再除以序列长度。
考虑一个初始值为零的二进制计数器。每次递增都会将末尾连续的所有一位变为零,再将紧接着的零位变为一。单次递增可能改变许多位。
在 次递增中,最低有效比特改变 次,下一位改变 次,更高位的改变次数依次减少。比特改变的总次数为
因此,在按每次比特改变计费的模型中,该计数器的递增操作具有常数摊还成本,尽管偶尔一次递增会改变对数数量的比特。计数器必须有足够的容量来容纳所考虑序列中的计数值。
记账法
记账法为各次操作指定费用,并将超出实际成本的部分视为存储起来的信用额度。后续的高成本操作可以使用这些额度。证明必须保证累计信用额度始终不为负。
对于支持入栈、出栈和一次弹出多个元素操作的栈(数据类型),对每次入栈收取两个单位的费用:
- 一个单位用于支付插入元素的成本。
- 另一个单位附在该元素上,用于支付它最终被移除的成本。
由于一个元素若未再次入栈,就不可能被移除多次,因此存储的信用额度足以支付所有成功移除操作的成本。每次操作的常数开销可以另行计费。因此,从空栈开始的任意 次此类操作,其总成本都是 ,即使其中一次批量出栈操作移除了许多元素。
这些信用额度只是数学上的记账手段,实现时不必实际存储它们。
势能法
势能法通过一个关于数据结构状态的数值函数,表示存储的信用额度。
设 为第 次操作后的状态, 为其势能。定义
求和后,中间项相消,得到恒等式:
如果 ,且所有可达状态的势能都非负,那么实际总成本就不超过摊还总成本。更一般地,只需保证最终势能不小于初始势能即可。
增加势能的操作需要为它可能在以后引起的工作支付费用。降低势能的操作则可以使用此前积累的信用额度来执行实际工作。单次操作的摊还费用可以为负;证明是否成立取决于累计不等式,而不是每次费用是否都为正。
当相关的待完成工作体现为结构的整体性质,而不适合自然地归属于单个元素时,势能法尤其有用。
动态数组
动态数组将元素存储在数组(数据结构)中,其容量可以大于当前元素数量。当追加操作发现数组已满时,实现可以分配一个更大的数组,并复制现有元素。
假设每次数组满时都将容量翻倍。从空数组开始执行 次追加,各次扩容所复制的元素数量依次为
直到某个小于 的项为止。它们的总和小于 。再计入写入新追加元素的 次操作,在这个简化模型中,元素写入或复制的总次数少于 。因此,追加操作的摊还成本为 。
势函数证明
用 表示元素数量, 表示容量。从元素数量和容量均为零开始,第一次追加时分配容量一,此后每次数组满时将容量翻倍。定义
对于仅通过追加操作可达的状态,这个势能始终非负。
不触发扩容的追加操作,其实际成本为一,势能增加二,因此摊还成本为三。
如果一个已满数组的元素数量和容量均为 ,那么一次触发扩容的追加操作成本为 :复制 个元素,再写入一个新元素。势能变化为
因此,其摊还成本为
第一次追加的摊还成本为二,因此同一个常数上界适用于每次追加。
扩容与缩容策略
容量翻倍并非必要条件。在相同的元素复制模型下,只要每次按一个固定的大于一的倍数扩容,追加操作就具有常数摊还成本。较小的增长因子通常可以减少闲置容量,但会增加复制频率。
相比之下,如果每次只增加固定数量的容量,那么在较长的追加序列中,复制总量可能达到平方级。
支持删除操作需要更加谨慎。如果数组满时容量翻倍,而一旦降至半满就立即将容量减半,那么在临界点附近交替插入和删除,可能反复触发大规模复制。一种常见策略是,只有当空间占用率降至四分之一时才将容量减半,同时不低于最小容量。将扩容和缩容阈值分开,可以确保两次大规模容量调整之间有足够多的更新操作。
用两个栈实现队列
队列(数据类型)可以用一个输入栈和一个输出栈实现:
- 入队时,将元素压入输入栈。
- 出队时,从输出栈弹出元素。
- 如果输出栈为空,则先将输入栈中的所有元素移到输出栈,再继续出队。
一次转移可能需要线性时间,但每个入队元素在被移除前最多只会转移一次。
假设每次栈的压入或弹出操作成本均为一个单位,并定义
一次入队的成本为一,势能增加二,因此摊还成本为三。不发生转移的出队操作,其摊还成本为一。如果一次出队需要转移 个元素,它会执行 次栈操作,但势能减少 ,因此摊还成本仍为一。
所以,队列的这两种操作都具有常数摊还成本,尽管某一次出队可能成本很高。
在高级数据结构中的应用
对于多种性能取决于操作序列而非孤立操作的数据结构,摊还分析都至关重要。
- 伸展树。 这类自调整的二叉搜索树会在访问后调整自身结构。标准操作具有对数级摊还成本,但单次操作可能需要线性时间。
- 斐波那契堆。 这类优先队列会推迟结构整理工作。插入和减小键值操作具有常数摊还成本,而提取最小值操作具有对数级摊还成本。
- 并查集。 将路径压缩与按秩合并或按大小合并结合起来,可以得到用反阿克曼函数表示的极小摊还成本。这个界针对的是操作序列,并不保证每一次操作的最坏情况成本都处于这一量级。
- 哈希表。 按固定倍数扩容可以进行摊还分析,而冲突处理则需要另行分析。因此,常数期望摊还更新时间可能同时依赖有关哈希的假设,以及针对重建过程的摊还论证。
在上述每种情况中,分析都会找出这样的结构变化:它们要么积累有助于后续操作的进展,要么消耗此前积累的进展。
假设与局限
初始状态
摊还保证依赖于初始状态。如果一个序列开始时,数据结构已经很大且装满了元素,那么它可能立即产生大量工作,而序列中没有更早的操作来支付这些成本。
因此,界中可以包含一个初始状态项:
另一种做法是将构建成本纳入分析,或者只考虑从空结构开始的序列。
允许的操作
证明只适用于其涵盖的操作。针对计数器递增操作的论证,并不自动适用于递减、重置或赋值。同样,动态数组追加操作的界,也不能证明在任意位置插入都具有常数摊还成本,因为移动元素可能成为主要成本。
延迟
较小的摊还成本并不能避免个别操作造成停顿。扩容、重建或结构调整,在实时操作系统中仍可能造成不可接受的延迟。
**去摊还化**可以将某些序列层面的保证转化为单次操作的最坏情况保证,通常做法是将一个大任务分散到后续操作中执行。例如,在容量调整期间,实现可以在每次更新时只复制有界数量的元素。这需要额外的状态,以及单独的证明,以确保未完成的工作不会积压到无法及时完成。
执行模型与状态复用
顺序执行下的摊还界,并不会自动计入并发计算中的竞争、调度或协调成本。
状态复用也需要谨慎处理。在持久化数据结构中,后续的多个分支可能共享某个早期版本。如果没有充分论证,就不能让每个分支各自独立地花费与该版本关联的信用额度。因此,与操作集合和初始状态一样,允许的执行结构也是摊还论证的一部分。