Notes on Amortized Analysis

深入浅出算法复杂度一文中，我们提到还存在一种复杂度分析策略，称为摊还分析（Amortized Analysis）。

在摊还分析中，我们主要关心某数据结构的一个操作序列中执行所有操作的平均时间，以此评价单次操作所花费的代价。摊还分析中最常用的三个技术分别是聚合分析、记账分析和势能分析。接下来我们主要讨论这三种摊还分析技术的原理以及例子。

聚合分析法

原理

所谓聚合分析，就是尝试求出一个包含个操作的序列在最坏情况下花费的时间，然后将此最坏情况下每个操作的平均代价，或者说摊还代价记为。

我们考虑「二进制计数器的比特反转问题」。设有一位二进制计数器，其初值为。我们用一个长度为k的位数组count来表示这个计数器，其中count的每一位为0或1。另外我们规定，计数器值的最低位存在count[0]中，最高位存在count[k-1]中。于是，我们可以得到计数器的自增算法：

void increment(int[] count) {
	int i = 0;
	while (i < count.length && count[i]==1) count[i++] = 0;	// 从低位向高位不断进位
  if (i < count.length) count[i] = 1;	
}

上述算法可以使该二进制计数器所表示的数值加1。我们想要知道，连续的次自增操作中，分摊意义下的每一次操作会有多少个比特位发生反转？

我们考虑对count的连续次自增操作，注意到，第位发生比特反转，当且仅当连续进行了次自增操作。于是第位发生比特反转的次数为次。接下来我们使用聚合分析法，将次操作中所有比特位上发生比特反转的次数相加，求出总的反转次数为：

于是得到在 的情况下， 。接下来就是将总的代价分摊到每一次操作上，于是，摊还代价为

这就是说，在分摊分析的意义下，平均每次自增操作只会有常数个比特位发生反转。

应用：可变长数组

无论STL中的vector亦或是JDK中的ArrayList，都是基于可变长数组实现的。数组的长度可以随着数组中元素的个数变化而变化：当数组将满时，执行扩容操作；当数组的装载率过低时，执行缩容操作。

我们假设扩容操作为grow()。grow()的实现有两种方式，一种是每次将数组的size变为原来的倍，另一种则是每次将数组的size增加。我们通过聚合分析法来讨论这两种策略的分摊复杂度。

我们假设向初始容量为的数组中连续插入个元素，插入操作所花费的时间都为，两种策略的区别在于扩容所需的时间完全不同。注意到，对于大小为的数组，每次扩容需要花费的时间为。

那么对于第一种策略，假设 ，扩容操作所花费的总时间为：

因此，第一种策略的分摊时间复杂度仅为。

对于第二种策略，假设我们仍假设 ，扩容操作所花费的总时间为：

因此，第二种策略的分摊时间复杂度高达。足以见得扩容策略的选择有多么重要。

记账分析法

原理

记账分析法的思想是，对每一个操作都征收一定的「费用」，我们将这个费用看作是它的摊还代价。不同类型的操作可能会征收不同的费用，当一个操作的费用超过它的实际代价时，我们将多出来的那部分费用存起来，可以称之为“余额”。账户中的余额可以用于支付后续操作中实际代价大于摊还代价的那些情况。注意，这种记账法不同于聚合分析法，在聚合分析法中，我们直接取总代价的平均值，所以不同类型的操作摊还代价总是相同的。

记账分析法的麻烦之处在于，我们需要谨慎地为每一种操作赋予它对应的摊还代价。同时，我们应当确保操作序列的总的摊还代价是该操作序列总的真实代价的上界，且这个上界尽可能的小。

如果用表示第个操作的真实代价，表示第个操作的摊还代价，那么有：

另外需要注意的是，操作序列的余额必须永远是大于零的。

我们继续考虑二进制计数器的例子。在自增算法increment中，无非是对count[i]的置位操作和复位操作。我们可以这样考虑，每次置位时，我们支付元的费用，其中元用以支付该位置位时所产生的代价，剩下的元存入余额中，用以在该位复位时支付相应的代价。这样在遇到复位操作时，我们就无需缴纳任何费用。

因此，我们甚至无需计算，就能知道对于次increment的调用，我们至多需要支付元的代价（每一次调用至多有次置位操作），也就是总的摊还代价的上界是。

记账分析法帮我们省去了复杂的计算，我们通过另一个例子来看看它的普适性。考虑连续出栈算法multi_pop：

void multi_pop(S, k) {
	while (!S.empty() && k > 0) pop(S);
}

该算法从栈S中连续弹出k个元素。那么一个包含push、pop、multi_pop的操作序列，它的分摊复杂度上界是多少？其中push操作和pop操作的时间复杂度都是。

仍考虑记账法。我们假设每次push操作支付元的费用，其中元用于支付元素入栈的操作，剩下的元存入该元素的余额中，用以支付它的出栈操作，于是每次pop和multi_pop都无需支付费用。因此，对于长度为的操作序列，我们至多付出的代价，也就是分摊复杂度的上界为。

回顾记账法，它很适合用于数据结构中的元素只有两种状态下的分析，比如栈中的元素出栈和入栈，比特位的置位和复位。

应用：双栈实现队列

我们先考虑常规思路。设两个栈分别为s1、s2，每次入队时，我们将元素压入s1中，那么此时s1中栈底存放的是队首元素，栈顶存放的是队尾元素。每次执行出队操作时，我们将s1中的元素全部弹出，压入s2中，这样s2的栈顶元素就是队首元素。栈顶元素出栈后，再将s2中的元素移回s1中。

这种方案下，元素入队操作的时间复杂度，但是出队操作的时间复杂度将为，其中是此时队列中元素的个数。考虑最坏的情况，对于包含次出入队操作的操作序列push,push,...,pop,pop，即先执行次入队操作，再执行次出队操作。根据聚合分析法，总的时间复杂度为：

此时每个操作的分摊复杂度将高达线性时间！这样的复杂度显然不是最好的。我们注意到，对复杂度起到主要影响因素的是出队操作，每次出队我们都要将所有元素移动两次，我们能否对此进行改进呢？

实际上，将s1的元素移动到s2中，执行出队操作之后，我们并不需要再将元素再次移回s1中，只需要在下次出队时判断一下，若s2为空，再将此时s1中的元素全部移动到s2中。这样就大幅减少了元素「来回移动」所带来的复杂度。我们采用记账分析法，每个元素在入队时需要支付元，其中元用于支付入队操作的时间复杂度，剩余的元用于支付从s1移动到s2的代价，出队操作只需支付元。也就是说，此时的出入队操作的分摊复杂度仅为。

应用：可变长数组

我们在第一章聚合分析法中提到过，对于可变长数组，主要的时间复杂度损耗在于扩容操作。现在我们试着使用记账分析法来计算可变长数组的分摊时间复杂度。

我们仍假设数组每次扩容为原来的两倍。我们要求每个元素在插入时缴纳元的费用，其中元用以支付插入操作的复杂度，剩余的元存入余额中。当数组发生扩容操作时大小为，数组「后半部分元素」此前缴纳的余额总数为 ，一定能够支付当前数组中所有元素的移动操作。

下面展示了整个扩容的过程，arr表示数组，amount表示对应元素所剩余额。

初始状态 ==> 状态1：数组已满
arr     = [1, 2, 3, 4]
amount  = [2, 2, 2, 2]
第一轮扩容：使用3, 4的余额支付
arr     = [1, 2, 3, 4, null, null, null, null]
amount  = [2, 2, 0, 0, 0, 0, 0, 0]
状态1：数组已满 ==> 状态2：数组已满
arr     = [1, 2, 3, 4, 5, 6, 7, 8]
amount  = [2, 2, 0, 0, 2, 2, 2, 2]
第二轮扩容：使用5, 6, 7, 8的余额支付
arr     = [1, 2, 3, 4, 5, 6, 7, 8, null, null, null, null, null, null, null, null]
amount  = [2, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]

由此我们知道，可变长数组的分摊复杂度为。

势能分析法

原理

势能分析法完全可以类比我们在物理学中学习的势，数据结构在不同的状态下拥有不同的势能。类似于物理学中的势能，势能的变化只与一个操作序列中数据结构的「初始状态」和「结束状态」有关。势能分析法不把预支付的代价表示为余额，而是将其看作势能的增加。

我们用表示数据结构的第个状态。假设我们对一个数据结构的初始状态执行连续次操作。对所有的 ，第个操作的作用是将该数据结构的状态从转化为。

令表示第个操作的实际运行时间，表示第个操作的分摊运行时间。设是数据结构的势函数，它的作用就是将数据结构的状态映射到到一个实数值。用表示势函数完成第个操作之后的值，初始值满足 。那么一个操作的分摊运行时间定义为：

即分摊运行时间是实际运行时间加上该操作所引起的势能的变化。所以个操作的总的分摊运行时间为：

上述等式右端的第二项是伸缩和，所以变化量只与初始状态的势能和结束状态的势能有关。注意到，如果我们定义的势函数能够满足 ，那么其摊还总代价就是实际总代价的一个上界。

另外，上式所定义的摊还代价与我们选择的势函数有关，**不同的势函数会产生不同的摊还代价。**为了使用分摊运行时间去估计实际运行时间，我们自然希望总的分摊运行时间与总的实际运行时间是同阶的。不难发现，我们可以选择任意一个满足 的势函数，这样它就不会影响摊还时间的阶次。

应用：二进制计数器的比特反转

略

应用：连续出栈算法

略

应用：小顶堆

略

应用：伸展树

略