第十二章 Amortized Analysis平摊分析

第12章 Amortized Analysis平摊分析

第10周

记于2022/11/29

概率分析与平摊分析的区别

• 概率分析
  • 平均执行时间
    • 考虑同一算法的所有可能输入情况
    • 如果使用概率，则称为期望运行时间
    • 针对单一操作/算法
• 平摊分析
  • 针对某一数据结构的 操作序列
  • 不使用概率
  • 操作序列中的平均操作性能/代价【主要针对对象】
    • 操作代价可能不同，其中有些代价巨大

平摊分析策略

聚集分析

• n个操作的序列最坏情况下花费总时间为T(n)

• T(n) / n每个操作的平均代价（或摊还代价）

• - A[0]位每次都会进行反转，总共进行n次 - A[1]位每间隔一次进行反转，共计n/2向下取整 .... - A[i]位，n/(2^i)

• 对于n个累加的序列，最坏情况运行时间为O(n),因此每一个操作的平摊成本/【平均成本】为O(1)

记账方法 / 核算法

• 【为不同的操作分配不同的费用 ，费用的金额称为**平摊成本**】
• 每个操作赋予一个（不同的）平摊代价
• 平摊代价高于其实际代价 / 平摊成本大于实际成本
  • 差值称为某一操作的存款（credit），如果存款不足则无法进行该操作
• 存款用于补偿以后那些平摊代价低于实际代价的操作
• 假设用 ci 表示第i个操作的实际成本/真实代价，用 ci` 表示其平摊成本/摊还代价
• 满足：
• 适用于所有的操作序列，因此要求总的平摊成本作为总的实际成本的上限，总的平摊成本 - 总的实际成本>=0
• 在中间任意时刻，都要保持总的平摊成本 - 总的实际成本>=0
• - PUSH 的**摊还代价**为 2 ，是因为其中有一个1给PUSH操作，还有一个1是因为现在压入一个数据将来要出栈，需要预留一个POP操作的成本 - 每个操作的平摊成本为O(1) - 对于二进制计数器，如果用1￥代表每次操作的成本，flip of one bit就代表花1￥，那么如果某位由0变为1给出的平摊成本为多少？ **2￥，1￥用于支付现在由0->1的费用（实际成本）,1￥存起来用于支付将来由1->0的费用** - 每次操作最多置 1 bit，因此一个操作的平摊成本最多为2￥ - 因此，n次操作总的平摊成本为O(n)，平均每次的成本为O(1)

势能方法

• 类似记账方法

• 存款不是某一操作的，而是整个数据结构的势（Potential）；预付的不是存款，而是一种“势能”，将势能释放即可以用来支付未来操作的代价

• - 总的平摊成本=总的实际成本 + 势能的总变化

• 栈操作

  • 势能等于栈中元素的个数

• 二进制计数器

  • 势能应该为某次操作后计数器中 1 的个数！ 因为0的个数只影响当前这一位，这一位完全可以用现在已有的势能来支付其开销
  • 如果bi>0（中间计数状态）,bi等于原来的1的个数，减去重置个数，再加一个新set为1的个数
  • 实际成本ci为ti+1，平摊成本<=2

动态表

• 操作：表插入、表删除

• 应用场景

  • 哈希表
  • 事先不知道表的大小；随插入而扩展；随删除而收缩

• 目标

  • 得到O(1)的平摊成本
  • 未使用的空间 <= 已经使用的空间

• 负载系数α = num/size

  • 如果size=0，则num=0，α=1
  • 不允许α>1 (目标2)

• 表空间满了则size加倍，保证α >= 1/2

• Insert

  • 聚集分析
  • 记账方法：插入x 收费3￥ ：1￥-> x实际插入费用 1￥ -> 将来删除x的费用 1￥ -> 其他项目【移动的费用】
  • 势能方法：

• Expansion

• Strategy