均摊算法_各个算法时间复杂度

首先区分一下均摊分析和平均情况时间复杂度，前者是一个序列的操作取平均值，后者是针对不同输入来计算平均值

用一个例子来分析，二进制计数器问题：有一个初始值为0的k位二进制计数器只支持加一操作，该操作的时间复杂度如何？把改变一个二进制位看做常数时间

对于该问题，最坏情况下，所有位都需要改变，因此最坏情况时间复杂度为O(k)，但由于计数器在不断加一，根本不可能遇到连续若干次最坏情况，因此应该分析一个操作序列的总时间，而不是单个操作的时间，这就称为均摊分析

1） 累计分析

计算n个操作的总时间T(n)，然后每个操作的均摊时间复杂度就是T(n)/n了

第0位每次变化，因此一共变化n次；第1位每两个操作变一次，一共变化n/2次…第k位变化n/2^k次，故总变化数小于2n次，从而均摊复杂度为T(n)/n=O(1)

2） 会计分析法

把每个操作的实际时间笑话哦看做资金消耗，并另外定义这种操作的“投资额”，供以后操作使用；如果可以保证始终有可用资金，则实际消费的资金不会超过投资总量，从而算法的时间耗费的上限为总投资额

在上面的例子中，假设把任何一个0变成1的操作投资2元，而把1变成0时不进行投资，从而这2元中的一个当时就会用掉，而另一个可以提供给这个1变回0时使用（注意针对的是同一位）；从而保证了始终有可用资金，由于每次最多只有一个0变成1（但可能有多个1变成0），因此投资总量不超过2n元，从而n个操作的时间不超过O(n)

另外一个会计分析法在每次操作时给第i个位投资2^(-i)元，则它从上一次翻转起一共累积得到了1元投资，正好够这一次翻转，从而保证始终有可用资金，一共投资了2n元，因此总时间不超过O(n)

3） 势能分析法

用Di表示经过i次操作以后的数据结构，Ci表示Di的势能（将势能定义为包含的1的个数），ci表示第i次操作的实际时间耗费，定义第i次操作的均摊时间耗费为ai=ci+Ci-Ci-1

从而n个操作的总均摊时间耗费为c1+c2+…+cn+Cn-C0；又C0=0,Cn>=0，从而总实际耗费时间sum{ci}小于总均摊时间耗费sum{ai}，从而均摊时间就是实际时间的上限

考虑第i步操作，把a个0变成1(a=1，每次最多有一个0变成1)，把b个1变成0，则ci=a+b，势能增量为a-b（增加了a个1，减少了b个1），从而ai=2a=2。从而每个操作的均摊复杂度为2

今天的文章均摊算法_各个算法时间复杂度分享到此就结束了，感谢您的阅读。