摊还分析

聚合分析
- 最坏情况下每个操作的平均势能，并不涉及概率
- 栈操作
  - 引入上界的限制： PUSH。MUTIPOP 的操作建立在 PUSH 之上，没有 PUSH 就没有 MULTIPOP
- 二进制计数器递增
  - 原始的上界是 O( K ), 但是这个界并不是紧的
  - 对每一种操作分别分析，求和再除以 N
- 总结
  - 栈操作和二进制计数器递增的 common 在于分析了操作的种类。比如，栈操作使用了 PUSH, MULIPOP, POP。二进制计数器使用了第1位的翻转，第二位的翻转，第三位的翻转
  - 都将各个操作的时间代价求和，并除以操作次数
  - 栈操作还算比较直接，但是二进制计数器递增就有些技巧，不太容易看到紧的上界
- 启示
  - 栈操作
  - 二进制计数器递增
    - 　　时间复杂度好低
核算法
- 看完核算法，感觉非常有意思，在进入的时候，就已经把退路想好了
- 栈操作
  - PUSH 元素的时候，就把要弹出时的时间代价放进来了，这样， POP 或者 MULTIPOP 就不需要代价了 --- 这也就保证了时间代价全由 PUSH 操作引起，且很容易计算 PUSH 操作的总时间代价，相当于用一个好求的量来代替复杂度量
- 二进制计数器递增
  - 已知的是，每 +1 至多有一位从 0 ->1
  - 当 0 -> 1的时候，存上 2 的代价，这样 1->0 的时候，就不需要耗费能量了， N 次操作最多翻 N 位，每位 2N
势能法
总结
- 总是有一些操作（A）多付钱，而其他操作（B）不付钱或少付钱。这些多付钱的操作有一个明显的特点，就是好计算
- 好计算表现在 A 这个集合所含的操作少且简单， B 所含的操作多且复杂， B与A的操作互补且 A>=B