作者: kaneson (Lance) 2021-04-28 12:25:00
位能法当于对毎个操作设计如何改变某个全域变量的量，可以有加有减，然后检查连续n个任意操作过程中这个值都不会比起始低，就是个ok的设计。此时 平摊cost=原cost + 你设计的位能变化然后这个位能值通常做法是跟你要操作的资料结构用个function对应成一个值，这样就很容易验证是否满足前提. 而相对记帐法，设计时只需对每个操作绑一个固定值，乍看很简单，但若要验证过程中会不会发生总和低于0就比较麻烦。这就是位能法比记帐法常用的原因
作者: kaneson (Lance) 2021-04-29 09:55:00
potential function 其实只要不违背前提可自由发挥, 只是得到的cost是否够tight, 课本的stack例子二种做法都有点像是不违反前提下把某些操作cost挪给别的操作来保持tight这题可用tree node深度加总来当位能, 每个 node 平均深度lgn, 增加一个node就总和增加lgn, 少一个node就少lgn.用这个来做位能差。网络上有解法是写lg1加到lgn就结束了,林的写法是在数学上比较严谨