|
1. 平摊分析
问题：hash表应该设置为多大？（使用链表解决冲突。）
越大越好，这样查找越快；但是空间越大，浪费越大。因此，通常为存储元素的2倍。但是如果不知道要存储的元素的值呢？
方法：使用动态表，思想为vector扩展容量的方式，空间满时重新分配两倍当前大小的空间，并移动元素，释放旧的空间。
复杂度分析：每一次都有插入操作，在2的幂次方加1处还需要移动前面的所有元素。
n次操作总共的时间为n次插入加越2*n次移动。
因此n个元素插入的平摊代价（单次插入）为O(1)。
平摊分析有三种方法
1.1. 聚集分析
计算n次操作总共的时间，再做平均值。一般来说不能确定一次的平摊代价具体是多少，而是n次的。如上的方法即为聚集分析方法。
这种方法虽然用到平均的概念，但是并没有与概率相关，因此这个平均是最坏情况下的。
应用：k位的二进制计数器，如果只包含增加操作则n次操作总时间为O(n)，平摊为O(1)；如果包含减少操作，则n次的总时间为O(k*n)，平摊代价为O(k)。
1.2. 记账法
对n个操作序列的不同操作赋予不同的平摊代价。
一次操作的实际代价如果小于其平摊代价，则差额作为存款，存起来。
一次操作的时间代价如果大于其平摊代价，则从存款中取出差额，以便完成此次操作。
需要注意的是，存款不能为负的。
因此n次操作过程中当前实际的总代价都小于等于当前的总平摊代价。
比如：上述聚集中，每次操作的平摊代价为3；当插入元素时，如果不增加表长，每次插入消费1（存储2个代价）；增加表长时，移动一个元素代价也为1（可以由存款来实现），增加表长后插入元素，代价为1（存储2个代价）。
当然平摊代价可以更大，这会得到更宽的一个平摊上界。
1.3. 势能法
与记账法不同，记账对每一次操作做平摊的估计，比如例子中平摊代价为3，并将本次操作剩余量存储在该次操作上。
势能法是:与整个操作序列相关的，定义Di为对数据结构Di-1做第i次操作后的结果，即记录总的存款额。势能函数将每个操作Di映射为一个实值函数f（Di），即与Di相关的势(f(D0)为0)。第i次操作的平摊代价由势能函数定义：
第i次平摊代价=第i次的代价+f（Di）-f（Di-1）
即第i次的平摊代价为第i次的实际代价，加上该次操作所增加的势能。
从而前n次的总的平摊代价为（c1+…cn）+f(Dn) – f(D0).
如果势能函数f（Dn）总是大于f（D0），则总的平摊代价就是实际代价（c1+…+cn）的一个上界。
对比记账法，记账法为记录每一次流水，势能则只记录总的存款额。
势能函数的构造可能不止一种，且一般需要很强技巧。
例子的势能函数的一种构造f(Di)=2*i-2^([lgi])。
2. 表的扩增与收缩
扩增如第一部分，满时增大表为2倍。
收缩则是当删除一个后，元素个数小于表大小的1/4，而不是1/2时才收缩表。因为如果以1/2，则如果再立即插入，则会由扩增，从而增大开销。
平摊分析对于有实时需求的场合不太适合。 | 
转播
