作者: 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就結束了,林的寫法是在數學上比較嚴謹