会计法介绍
为每个操作类型分配一个平摊代价，保证在整个操作序列中平摊代价始终大于实际代价
设计思路：
需要结合数据结构的特点和算法的规律灵活设计
【栈操作】
问题定义：初始为空的栈进行push，pop，multipop操作的代价分析
设计思路：
由操作的代价规律 : push >= pop+multipop
则 2*push的代价 > 总代价
分析：
实际代价
平摊代价
设计的平摊代价满足会计法的要求，则总代价O（2n），平摊代价O(2)
【二进制计数器】
问题定义：初始为0的k位二进制计数器代价分析
设计思路：
对于任何一个数位，0 ~> 1 的次数总大于等于 1~>0 的次数
分析：
设 0 ~>1的平摊代价为2，1~>0的平摊代价为0
设计的平摊代价满足会计法的要求，则总代价O（2n），平摊代价O（2）
支付宝扫一扫
微信扫一扫
.png)
最新评论