冒泡~今天看了MIT算法导论公开课之第13课 平摊分析、表的扩增、势能方法的课程 所以做了以下记录。
平摊分析
定义：
用平摊的思想来分析一个操作序列，以证明每个操作的平均代价很小，尽管其中一个或几个操作的代价比较大。
先举哈希表来进入这个平摊的分析的思想（也就是平摊分析中的聚集分析，具体的下面会描述）
1.哈希表多大才合适呢？
通常情况下，如果增大的话，查找的速度会更快，但是这样需要的空间就大了会浪费空间。
在这样的情况，通常对于要存储n个元素的哈希表的大小最好为Θ(n)。
但是如果不知道要存储的元素数量时，如何设定哈希表的大小？
这个时候就要使用动态表的策略
（思想：vector扩展容量的方式，空间满时重新分配两倍当前大小的空间，并移动元素，释放旧的空间。）
当哈希表已满，再加入元素时（溢出），将哈希表扩大：
1.分配一个更大的表。
2.将旧表中的元素拷贝至新表。
3.释放旧表的空间。
（注意：这个时候哈希表的size是2的整数次幂）
举个栗子：
复杂度分析：
在最坏情况下，一次插入运算的代价为Θ(n)。
关于第i次插入操作的代价，当i-1为2的幂时，代价为i，其他时候，代价为1。
由上面的图，让我们看看平均的时间复杂度，每次基本插入操作为1，空间溢出时需要开一个更大一倍的空间，并复制当前的元素过去，所以空间溢出时所需要的时间为2的i次方（i为第几次溢出）
用到平均但并不涉及到概率学，主要想表示的是在最坏情况下的平均表现。
三种方法：
a.聚集分析
b.记账分析
c.势能分析
聚集分析也就是刚刚上面所提到的关于哈希表大小以及插入扩展的分析。
所以接下来叙述记账分析和势能分析
记账分析
！可以这样通俗的解释一下：
想象自己担任了一个会计，对第i个操作收费为ci，收益个虚构的平摊代价每一步运算需要花费$1,未用到的余款就被存到银行，用于偿付以后的操作。
如：每次插入收费为3，插入消耗1，剩下的2存入银行为表翻倍时做准备（也就是说剩下的用于后续可能发生的表的空间翻倍和拷贝元素），要始终保证银行的金额为正
即提前平摊，总能支付扩充表的费用，这样某一个高开销的操作会被平摊掉
注意：存款不能为负的。
势能分析
与记账法不同，记账对每一次操作做平摊的估计，比如例子中平摊代价为3，并将本次操作剩余量存储在该次操作上。势能法是:与整个操作序列相关的。对比记账法，记账法为记录每一次流水，势能则只记录总的存款额。
finally~
今天是10.24 程序员节~大家节日快乐鸭！多长头发不掉发！