平摊分析概念以及知识点

逃离我推掉我的手 2022-07-12 02:57 249阅读 0赞

平摊分析是一种[算法][Link 1]分析的手法，其**主要思路**是：对若干条指令（通常O(n)条）整体进行考虑其时间复杂度（以获得更接近实际情况的时间复杂度），而不是逐一考虑执行每条指令所需的时间复杂度后再进行累加。

对于一个操作的序列来讲，平摊分析（Amortize Analysis）得出的是在特定问题中这个序列下每个操作的平摊开销。一个操作序列中，可能存在一、两个开销比较大的操作，在一般地分析下，如果割裂了各个操作的相关性或忽视问题的具体条件，那么操作序列的开销分析结果就可能会不够紧确，导致对于操作序列的性能做出不准确的判断。用平摊分析就可以得出更好的、更有实践指导意义的结果。因为这个操作序列中各个操作可能会是相互制约的，所以开销很大的那一、两个操作，在操作序列总开销中的贡献也会被削弱和限制。所以最终会发现，对于序列来讲，每个操作平摊的开销是比较小。平摊分析的输入是问题的具体条件以及若干个有相互关联的具体动作的序列，输出是，在该问题的条件下，这个动作序列的每一个动作（不管具体它是什么）的平摊性能开销并不等于最大开销动作的最坏时间（不再需要考虑具体动作，只需要知道每个动作可能是平摊小开销的）。

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

下面举一个动态表的例子:

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

对于这种情况，我们可以采用动态表的策略来应对。就是一开始分配一定量的内存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(n2)。虽然这个结果是这个操作序列的一个最差时间复杂度上界，但实际上，这个上界是不够紧确的。

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

> > > > > > > > >   ![20151102104813138][]

所以，这个操作序列的最坏时间复杂度其实是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；同样，每次缩减时成缩减成原来的1/2的话，而每次TABLE-DELETE之前，表的装载因子也为0.5。与原来单纯的INSERT序列或DELETE序列不一样的是，在上面这段话中描述的情况下，最差时间复杂度将会是O(n2)。为什么呢？？因为具体问题的条件变化了，这两个操作之间的制约也减弱了，比如，可能是以下这么一种操作序列：

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

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

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

有三类比较常见的均摊分析：

1.聚类分析：证明对所有的n，由n个操作所构成的序列的总时间在最坏情况下为T(n)，每一个操作的平均成本为T(n)/n；比如栈的操作，对于一个空栈的入栈和出栈的操作

2.记账方法： 在平摊分析的记帐方法中，决定每一个操作的均摊成本，对不同的操作赋予不同的费用，某些操作的费用比它们的实际代价或多或少。我们对一个操作的收费的数量 称为平摊代价。当一个操作的平摊代价超过了它的实际代价时，两者的差值就被当作存款(credit)，并赋予数据结构中的一些特定对象，可以用来补偿那些 平摊代价低于其实际代价的操作。这种方法与聚集分析不同的是，对后者，所有操作都具有相同的平摊代价。数据结构中存储的总存款等于总的平摊代价和总的实际 代价之差。注意：总存款不能是负的。在开始阶段对于过度要价存储预先支付的存款，在后面的序列中再支付操作。比如，二进制计数器: 通过二进制触发器计算一系列数字

3.势能方法： 在平摊分析中，势能方法（potential  method）不是将已预付的工作作为存在数据结构特定对象中存款来表示，而是将存款总体上表示成一种“势能”或“势”，它在需要时可以释放出来，以支付 后面的操作。势是与整个数据结构而不是其中的个别对象发生联系的。比如，动态表，可以动态改变大小的连续存储数组。

关于这3种方法的具体解释可以看http://blog.csdn.net/ying\_xu/article/details/51433497这篇

[Link 1]: http://lib.csdn.net/base/datastructure
[20151102104813138]: /images/20220711/9fbcdaa4018440d99814372d4aeb9837.png