1 时间复杂度

时间复杂度与摊销分析 - 图1

1 Θ(g(n))

  • 定义要求每个成员f(n)∈Θ(g(n))均渐近非负，即当n足够大时，f(n)非负。渐近正函数就是对所有足够大的n均为正的函数。

    2 O

  • 当只有一个上界时，用O记号

2 空间复杂度： 程序运行时需要额外创造的空间

2 摊销分析

1 摊还分析

  • 对数据结构的一个操作序列中所执行的所有操作的平均时间，来评价操作的代价

1 聚类分析

  • 证明对所有的n，由n个操作所构成的序列的总时间在最坏情况下为T(n)，每一个操作的平均成本为T(n)/n；比如栈的操作，对于一个空栈的入栈和出栈的操作

2.记账方法

  • 在平摊分析的记帐方法中，决定每一个操作的均摊成本，对不同的操作赋予不同的费用，某些操作的费用比它们的实际代价或多或少。我们对一个操作的收费的数量称为平摊代价。当一个操作的平摊代价超过了它的实际代价时，两者的差值就被当作存款(credit)，并赋予数据结构中的一些特定对象，可以用来补偿那些平摊代价低于其实际代价的操作。这种方法与聚集分析不同的是，对后者，所有操作都具有相同的平摊代价。数据结构中存储的总存款等于总的平摊代价和总的实际代价之差。注意：总存款不能是负的。在开始阶段对于过度要价存储预先支付的存款，在后面的序列中再支付操作。比如，二进制计数器: 通过二进制触发器计算一系列数字

3.势能方法

  • 在平摊分析中，势能方法（potential method）不是将已预付的工作作为存在数据结构特定对象中存款来表示，而是将存款总体上表示成一种“势能”或“势”，它在需要时可以释放出来，以支付后面的操作。势是与整个数据结构而不是其中的个别对象发生联系的。比如，动态表，可以动态改变大小的连续存储数组。

3 聚合分析

1 表的扩张

1 动态表

  • whenever the table gets too full(overflows), grow it
  • 创建new larger table
  • 把就表的内容复制到新的表上
  • free old table

4 核算法

1 cost

  • n insert cost O(n)times;
i 1 2 3 4 5 6 7 8 9 10
size(i) 1 2 4 4 8 8 8 8 16 16
cost(i) 1 2 1 1 5 1 1 1 9 1
  • cost of insert: cost(1)+… + cost(n)=n+2n<3n
  • 所以n次insert花费的时间为Θ(n)

2 策略

1 charge 3 cost for insert

  1. pay for 立即的insert
  2. stored for table doubling

2 可以cover表的扩展与复制到新表的费用

charge 2 3 3 3 3 3 3 3 3 3
bank(余额) 1 2 2 4 2 4 6 8 2 4
  • bank的费用加上下一个charge 可以cover表的扩展

5 势能法

1 势能与整个数据结构相关联

  • bank count 视为potential energy of dynamic set

2 框架

  • start with data structrue D_o
  • 操作 i 转换为 D(i-1)-> D(i)
  • cost of 操作 is ci