锐客网

  1. 首页 > it技术 > >

《算法导论》笔记 第17章 17.3 势能方法

【笔记】

势能方法：已预付的工作表示成一种势能或势，他在需要时可以释放出来，以支付后面的操作。
势函数Φ将每个数据结构Di映射为一个实数Φ(Di)，即与数据结构Di相联系的势。第i个操作的平摊代价c'i=ci+Φ(D_i)-Φ(D_{i-1})
n个操作总的平摊代价为∑c'i=∑ci+Φ(Dn)-Φ(D0)
如果定义一个势函数使得Φ(Dn)>=Φ(D0)，则总的平摊代价∑c'i就是总的实际代价∑ci的一个上界。
通常定义Φ(D0)为0，证明对所有的i，有Φ(Di)>=0。


【练习】 17.3-1 假设有势函数Φ，使得对所有的i都有Φ(Di)>=Φ(D0)，但是Φ(D0)≠0。证明：存在一个势函数Φ'使得Φ'(D0)=0，Φ'(Di)>=0，对所有i>=1，且用Φ'表示的平摊代价与用Φ表示的平摊代价相同。
令Φ'(Di)=Φ(Di)-Φ(D0)即可。


17.3-2 用势能方法的分析重做练习17.1-3。
设i=2^j+k，定义第i个操作Di的势函数Φ(Di)=2*k。
当k=0时，实际代价为i。
《算法导论》笔记 第17章 17.3 势能方法
文章图片


当k!=0时，实际代价为1。
《算法导论》笔记 第17章 17.3 势能方法
文章图片


所以第i个操作平摊代价为O(1)。


17.3-3 考虑一个包含n个元素的普通二叉最小堆数据结构，它支持最坏情况时间代价为O(lgn)的操作INSERT和EXTRACT-MIN。请给出一个势函数Φ，使得INSERT的平摊代价为O(lgn)，EXTRACT-MIN的平摊代价为O(1)，并证明函数确实是有用的。


17.3-4 假设某个栈在执行n个栈操作PUSH、POP和MULTIPOP之前包含s0个对象，结束后包含sn个对象，则这n个栈操作的总代价是多少？


17.3-5 假设一个计数器的二进制表示中在开始时有b个1，而不是0。证明：如果n=Ω(b)，则执行n次INCREMENT操作的代价为O(n)。


17.3-6 说明如何用两个普通的栈来实现一个队列，使得每个ENQUEUE和DEQUEUE操作的平摊代价都为O(1)。


17.3-7 设计一个数据结构来支持整数动态多重集合S上的下列两个操作：
INSERT(S,x) 将x插入S中。
DELETE-LARGER-HALF(S)删除S中最大的floor(|S|/2)个元素。
解释如何实现这个数据结构，使得任意m个操作的序列在O(m)时间内运行，而且要在O(|S|)时间内输出S的元素。
















【《算法导论》笔记 第17章 17.3 势能方法】

    推荐阅读


    上一篇：GitGUI使用教程(git提交代码到码云)

    下一篇：dsf