【算法简介】平摊分析

1. 简述

平摊分析是指在某种数据结构上完成一系列操作，在最坏情况下所需的平均时间。

平摊分析与传统分析方法的主要差别为：

1）平摊分析时间与传统分析方法的平均情况下时间不同，它是最坏情况下的平均时间。

2）平摊分析不涉及概率分析。

3）平摊分析中时间函数T(n)，其中n指的是操作的次数，而不是输入的规模。

常见的有三种方法：聚集法、记账法、势能法。

2. 合计法(聚集法)

2.1 合计法的思想：把n个不同或相同的操作合在一起加以分析计算得到总时间的方法。即n个操作序列在最坏情况下的总时间，记为T(n)，其中n为操作数。由此得到在最坏情况下每个操作的平均时间为T(n)/n。

2.2 例子说明：栈操作的平摊分析(不同类操作)

操作	代价
PUSH	1
POP	1
MULTIPOP	min(k,s)

解法一，传统方法分析：

由于三个操作最坏的操作为multipop操作，而一次multipop操作在最坏情况下的时间为O(n)，如果n个操作均为multipop操作，则总时间将达到O(n^2）。

在最坏情况下n个操作的总时间T(n)= O(n^2），每个操作的平摊时间为：T(n)/n=O(n)。

解法二，合计法分析：

由于三个操作不是相互独立的，一个对象入栈后最多弹出一次，因而在非空栈S上完成的pop次数(包括multipop操作)最多为push的次数，又由于初始栈S为空，且n个操作中push的次数≤n，pop次数≤n，由于每个push和pop操作的实际代价为O(1)，所以n次操作在最坏情况下的总时间≤2n=O(n)，每个操作的平摊时间为T(n)/n=O(1)。

2 记账法

记帐法思想：先对每个不同的操作核定一个不同的费用（时间），然后计算n次操作总的费用。当然，由于这个费用是人为赋予的，所以很容易得到一个松上界。

这种事先的操作费用核定可能与实际费用不符，存在二种情况：

1）超额收费：核定费用>实际费用，此时差额存放在该对象的身上。

2）收费不足：核定费用<实际费用，此时差额由该对象身上的存款支付。

费用的核定(平摊核定)是否正确需检查n次操作核定总费用是否大于n次操作实际总费用（这里n具有任意性，并不是单指一个定值n）。因此，在记账方法中，某些操作的费用比它们实际代价或多或少。但push、pop、multipop操作的平摊时间为O(1)。

3 势能法

思想：通过定义一个势函数完成对每个操作的平摊核定。

势是与整个数据结构联系而不是其中的个别对象发生联系的。且push、pop、multipop操作的平摊时间为O(1)。