強者大大，大家好
小弟第一次發文
排版混亂麻煩大家多擔待
想請問
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就結束了,林的寫法是在數學上比較嚴謹

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