Mengzelev's Blog

算法导论学习笔记-摊还分析

Word count: 657 / Reading time: 2 min
2018/09/17 Share

聚合分析

聚合分析指,证明对所有n,一个n个操作的序列的最坏情况下花费的总时间为T(n)。因此在最坏情况下,每个操作的平均代价,或摊还代价为T(n)/n。

摊还操作可以看作是不带概率计算的平均情况分析。因为概率不好计算。概率什么时候好计算过了

此摊还代价适用于每个操作,即使序列中有多种类型的操作也是如此。

算法导论上给出的示例为增加了MULTIPOP的栈操作二进制计数器递增问题,简单概括一下二者的共同点:

  • 需要分析复杂度的操作由连续的n个操作构成
  • 每个单步操作的时间复杂度难以确定为与n有关的表达式,与当前状态密切相关
  • 对每个单步操作取最坏情况得出的上界过于宽松,浪费时间
  • n个连续操作的总时间复杂度比较容易求得

大致感觉就是,使用摊还分析可以给这些操作一个清白,它们事实上没有那么慢。

核算法

核算法就是对不同的操作赋予不同的信用,这个信用值可能会多于或少于实际消耗的代价。实际操作时采用多退少补的原则,保证总信用(支付的代价-实际的代价)始终非负即可。

一般用于解决不同操作间具有依赖关系的问题,例如聚合分析中提到的栈操作问题(出栈操作次数上界即为进栈操作次数)和二进制计数器递增问题(复位操作次数依赖于置位操作次数)。

势能分析

势能分析看上去更加数(wu)学(li)一点,与核算法有点类似,不同之处势能分析为每一个状态都设置了一个对应的势能,即势能函数。虽然在操作过程中势能可能有升有降,但只要最终势能是增加的,就可以证明代价的上界。

选择势能函数应该是比较困难的。产生的摊还代价依赖于选择的势能函数。具体根据需要证明的上界来选择适度的势能函数,毕竟最优势能函数不是那么好找的。

动态表

这个有丶玄学,是势能分析的综合应用,建议看书。

睡觉了,先更到这里,明天继续更

CATALOG
  1. 1. 聚合分析
  2. 2. 核算法
  3. 3. 势能分析
  4. 4. 动态表