强者大大，大家好
小弟第一次发文
排版混乱麻烦大家多担待
想请问
1.Potential Function的定义
背后的用意想了好久还是无法理解
2. c <= k*logn
是因为前面定义insert . extract-min的worst case为O(n)吗
http://i.imgur.com/Lm8Q4WX.jpg
http://i.imgur.com/wbIbIZT.jpg
先叩谢各位大大了

位能法当于对毎个操作设计如何改变某个全域变量的量，可以有加有减，然后检查连续n个任意操作过程中这个值都不会比起始低，就是个ok的设计。此时 平摊cost=原cost + 你设计的位能变化然后这个位能值通常做法是跟你要操作的资料结构用个function对应成一个值，这样就很容易验证是否满足前提. 而相对记帐法，设计时只需对每个操作绑一个固定值，乍看很简单，但若要验证过程中会不会发生总和低于0就比较麻烦。这就是位能法比记帐法常用的原因

我觉得立宇这个解法有点难懂这题是CLRS的习题 你可以找一下amortized cost那章的解答 我觉得写得比较好（有点懒就懒得贴了sorry)

potential function 其实只要不违背前提可自由发挥, 只是得到的cost是否够tight, 课本的stack例子二种做法都有点像是不违反前提下把某些操作cost挪给别的操作来保持tight这题可用tree node深度加总来当位能, 每个 node 平均深度lgn, 增加一个node就总和增加lgn, 少一个node就少lgn.用这个来做位能差。网络上有解法是写lg1加到lgn就结束了,林的写法是在数学上比较严谨

去看台大算法影片教比较清楚