TOC
动态表
简单阐述一下动态表的基本思想，先建立一个表，当插入的元素大于表的大小时，建立一个新表（大小为旧表的两倍），并将旧表中的所有数据复制到新表中，然后插入新元素，最后摧毁掉旧表。如此反复，就能获得一个动态的哈希表。
平摊分析
所谓平摊分析，就是如果一个算法的曲线变换比较的激烈，比如 动态表，在插入的项正好大于表的大小时，在那一次的插入操作将会建立一个新表，并将原表的内的数据复制到新表这种，这将会造成O(n)的插入时间。但是在普通的插入状态下，没有复制操作，时间是O(1)的。所以并不能依赖最差情况O(n)的插入时间就断定插入n个元素时的复杂度为O(n^2).
这是不公平同时也是错误的，所以平摊分析就是将一个不那么平均的算法用平均的眼光看待，将其平均化，从而更加准确的分析与判断这个算法。
本章节，我们将介绍三种平摊算法 分别是 聚集分析 记账方法 势能方法
聚集分析
聚集分析本身就是将每个独立的操作加起来，最后 / n 就是单个的时间成本，不过这种方法可能会具有一些局限性，因为有时间加的操作可能会存在一些困难。
记账方法
记账方法将消耗的成本变得更加形象化。
首先，你是一个财务管理员，对于一次操作，我们会赋予他费用（就类似与每次给你三块钱，你自己去花），这些费用将用于支付具体操作，我们将这些费用称之为 摊还代价。如果某个操作用不完这些摊还代价（零花钱太多了用不完），将会存到银行之中，称之为 信用。所有的操作除了能够使用这次派发的 摊还代价之外，也能够使用信用支付。但是，每次操作使用的费用必须小于你的存款和这次摊还代价的总和。也就是说，你必须准备足够的钱来支付你的操作。
公式实在不好画，就不画了
总的来说，如果用Ci 来代表 第i个操作的真实代价（这次真正花了多少钱），用ci^来代表第i个操作的摊还代价（每次给的零花钱 每次给的钱都是一样的），那么如果有一个操作序列，那么 摊还代价的总和 > 真实代价的总和 必须！
所以我们的目的就是找到那个摊还代价，也就是每次发给他的零花钱，从而让整个公式成立，不让这个序列操作破产。当然是越不浪费越好
exp 动态表用记账
每次给3块钱自己花 插入一次花一块 复制一次花一块 多的存起来 case1 空间足够 用一块就够了 多的两块存银行 case2 空间不够了 全部复制+插入
大致上就是这样，最好还是画个表，尝试找出其中的一些规律，这个结果就是得出 3块钱刚好够花，所以我们认为单次插入的平摊成本大概就是3
势能方法
与记账方法类似，势能方法利用了物理中的势能概念来描述整个模型。
基本框架 - 引入概念 数据结构 D0 - 操作i 将D(i - 1) 转化为 D_i(把数据结构上的操作看成映射) - 操作代价为C_i - 建立一个势能函数 Φ() 他会把数据结构中的一个值映射成一个实数
核心公式 如果假设操作i的平摊代价为c^i 那么 > c^i = c_i + Φ(Di) - Φ(D(i - 1)) 其中 > Φ(Di) - Φ(D(i - 1)) 意为势能变化 ΔΦ_i
势能变化
当势能变化>0的时候 c^i < c_i 也就是说当前的实际操作付出的代价超出了平摊代价，这意味着我们需要从势能库中拿一些出来补贴。
当势能变化<0的时候 正好相反 实际操作的代价小于平摊代价，可能存放一些势能。
至于如何去运用势能方法，就是依赖猜测那个势能函数。
总结
平摊分析的不同方法可能擅长分析不同的算法。并且他在分析相同算法的时候，的出来的结果可能也是不一致的。