《算法导论》笔记－－平摊分析

 

　　对于一个操作的序列来讲，平摊分析（Amortize Analysis）得出的是在特定问题中这个序列下每个操作的平摊开销。

　　一个操作序列中，可能存在一、两个开销比较大的操作，在一般地分析下，如果割裂了各个操作的相关性或忽视问题的具体条件，那么操作序列的开销分析结果就可能会不够紧确，导致对于操作序列的性能做出不准确的判断。用平摊分析就可以得出更好的、更有实践指导意义的结果。因为这个操作序列中各个操作可能会是相互制约的，所以开销很大的那一、两个操作，在操作序列总开销中的贡献也会被削弱和限制。所以最终会发现，对于序列来讲，每个操作平摊的开销是比较小的。

　　我有这样的理解："对于一个操作序列来讲，平摊分析得出的是这个序列下每个操作的平摊开销"这句话中，操作这个词出现了两次，意义并不相同。

　　比如，我们拿《算法分析》中17.1节中举的第一个关于栈操作的例子来解释。

　　操作序列，是指由pop、push、multipop三个动作任意组成一组动作组合，并对一个栈进行这组动作。这里"操作序列"中的"操作"，是特指的pop动作、push动作、multipop动作等。

　　而"每个操作的平摊开销"中的"操作"，并不是特指某一种动作，而是指对于一个n个动作的序列中的每一个动作，这时不关心动作本身具体是什么。

　　分清这种区别初听起来有些咬文嚼字，但实际上我觉得，这样理解的意义在于，搞清楚以下的"精神"：平摊分析的输入是问题的具体条件以及若干个有相互关联的具体动作的序列，输出是，在该问题的条件下，这个动作序列的每一个动作（不管具体它是什么）的平摊性能开销并不等于最大开销动作的最坏时间（不再需要考虑具体动作，只需要知道每个动作可能是平摊小开销的）。

　　平摊分析不是平均运行时间性能分析。平摊分析并不需要建立在概率分析的基础上，也允许操作序列中各操作出现最差运行时间。但平摊分析的结果是要告诉我们，一个操作序列的最坏性能并不是像初看起来那样糟（割裂各操作关系和具体条件，用开销最大的操作的最坏时间复杂度去分析整个操作序列的最坏性能），而是总体来讲有一个比较好的最坏开销（因为有了各操作相互的制约以及初始条件的限制后，开销最大的操作贡献有限）。

　　平摊分析或许称不上是一种算法设计方法。但平摊分析为我们提供了另一种观察性能的角度。使我们在某些问题上能得出更具有实践意义的结果。

 

　　下面我们来看一个关于动态表的具体例子：

　　我们经常会遇到这样的情况：无法预先知道有多少对象需要存储。因此无法准确地事先分配好足够的内存并保证内存是大致足够的。事先分配的内存要么可能不足，要么太多以致浪费。

　　对于这种情况，我们可以采用动态表的策略来应对。就是一开始分配一定量的内存A，如果在向这个内存内继续增加对象时发现空间不足的话，就重新分配一块比原来大的内存B（就定B比A要大两倍吧），把原内存A中所有的对象都复制到内存B中，然后把新加入的对象增加到B的空余位置中，最后把内存A释放掉。同样，如果从内存中称除某个对象时，发现此空间内所存的对象太少，出现空间浪费时，就分配一块新的更小的内存（先假设新内存是原内存的二分之一），把原内存中的对象复制过来，并释放原内存给其它的程序使用（C++标准库中的vector等，就用了这样的策略）。

　　我们先来看插入操作的伪代码：

TABLE-INSERT (T , x)

1 if size[T ] = 0 then

2     allocate table[T] with 1 slot

3     size[T] ← 1

4 if num[T] = size[T] then

5     allocate new-table with 2 · size[T] slots

6     insert all items in table[T] into new-table

7     free table[T]

8     table[T] → new-table

9     size[T] → 2 · size[T]

10 insert x into table[T]

11 num[T] → num[T] + 1

　　在这个操作中，如果插入时，原内存块还有足够的空间，那就只要把新插入的x放到未使用的空间上（空间的使用是连续的，动作就是伪代码中的第10行），这样，需要的时间仅仅是常数时间O(1)。如果插入对象时，原内存块已经没有空间再容纳新成员了，这时就需要分配新的空间，把原内存的数据复制过去，释放原内存，然后再进行插入动作（如伪代码中的5-9行）。这种情况下，需要的时间候，就是原内存的长度相关（因为要依次拷贝原内存中的每一个对象），这是一个O(n)时间的操作。因此，TABLE-INSERT操作的最坏时间复杂度是性线的O(n)。

　　好，例子的情况到这里已经描述完了。现在我们来看，如果对一个动态表进行一个由n个TABLE-INSERT操作组合起来的动作序列，那么这个序列的操作性能是怎么样的呢？

乍一想，我们可能会认为，每个TABLE-INSERT的最坏性能是O(n)，n个TABLE-INSERT操作如果恰好每个操作都出现了最坏性能，那么整个操作序列的最差时间复杂度就是O(n²)。虽然这个结果是这个操作序列的一个最差时间复杂度上界，但实际上，这个上界是不够紧确的。

　　我们假设一开始这个表是空的，然后用TABLE-INSERT向这个表中依次插入n个对象。仔细一想，就会发现，这个操作序列中的n个TABLE-INSERT是不可能连续n次出现最坏性能的，甚至，出现最坏性能的机会是比较小的。假设c_i是第i次插入时的时间，那么很容易就可以分析出来，c_i只i等于2的整数次幂时，才会出现比较大的值（值为i），除此以外，c_i都是常数1。我们把c_i进行求和，就可以得出总的时间

 

　　所以，这个操作序列的最坏时间复杂度其实是O(n)。

　　原因就在于，这个TABLE-INSERT虽然偶尔会出现线性时间复杂度的操作，但这种情况，在这个问题中出现的机会很少（只有i等于2的整数次幂时），而其它情况下，TABLE-INSERT的操作都是常数时间，这些情况足以将TABLE-INSERT偶尔出现的"恶劣"行为的影响平摊掉。使得对于整个序列来说，最坏时间复杂度仍然保持在比较好的水平下，每个操作的平摊性能也显得很优良（每个操作都O(1)的）。（这个问题更严谨的分析应该看《算法导论》书中17.4部分）

　　同样的，TABLE-DELETE操作与TABLE-INSERT操作的分析是极为类似的。这里就不再单独讨论。

　　但有意思的是，如果是由TABLE-DELETE与TABLE-INSERT两种操作来组成一个操作序列的话，结果会是怎么样的呢？我们先假设，a一个动态表的装载因子，它是用内存块中对象个数除以内存块可存储的对象总个数得到的。那么，如果动态表每次扩充都变成原来大小的两倍的话，每个TABLE-INSERT之后，装载因子都是0.5；同样，每次缩减时成缩减成原来的2/1的话，而每次TABLE-DELETE之前，表的装载因子也为0.5。

与原来单纯的INSERT序列或DELETE序列不一样的是，在上面这段话中描述的情况下，最差　　　　时间复杂度将会是O(n²)。为什么呢？？因为具体问题的条件变化了，这两个操作之间的制约也减弱了，比如，可能是以下这么一种操作序列：

　　先进行插入，一直到插入动作进行时表进行了扩张，之后的操作则是：

　　D、D、I、I、D、D、I、I、D、D、I、I......

　　这时，分析可知，这个表将在这些动作间不断地扩张和缩减。这个序列中之后的操作每一个都是O(n)时间。因此，总的时间复杂度是O(n²)。之所以会这样（不再是O(n)了），是因为，这个操作序列和条件下，已经不能保证有足够的O(1)的操作来平摊掉O(n)操作的开销， O(n)操作的出现机会也不再受到控制。

　　有一个办法可以改进，就是动态表在TABLE-DELETE在装载因子是0.25（或其它可能值）而不是0.5时才进行缩减。这样，又能恢复类似之前的分析和结果了（最差时间复杂度为O(n)）。

 

　　从这个例子也可以看出：

　　这就是平摊分析观察问题的角度，它考查的是一个操作序列，并且把操作之间的相互影响，以及问题的条件制约考虑进来得出性能结论。这比起割裂各操作的相互限制以及问题具体条件来分析更具指导意义。

评论

1 楼 luluandbobo 2012-12-07  

为什么要先释放table[T]呢，它不是一个指针吗？如果释放掉了，下面怎么指向new-table呢？