推 kaneson: 位能法當於對毎個操作設計如何改變某個全域變數的量，可 04/28 12:25
→ kaneson: 以有加有減，然後檢查連續n個任意操作過程中這個值都不會 04/28 12:25
→ kaneson: 比起始低，就是個ok的設計。此時 平攤cost=原cost + 你設 04/28 12:25
→ kaneson: 計的位能變化 04/28 12:25
推 kaneson: 然後這個位能值通常做法是跟你要操作的資料結構用個funct 04/28 13:10
→ kaneson: ion對應成一個值，這樣就很容易驗證是否滿足前提. 而相 04/28 13:11
謝謝解釋，原理懂了
但還是無法理解解答那個potential function的為何是那樣QQ
→ kaneson: 對記帳法，設計時只需對每個操作綁一個固定值，乍看很簡 04/28 13:11
→ kaneson: 單，但若要驗證過程中會不會發生總和低於0就比較麻煩。這 04/28 13:11
→ kaneson: 就是位能法比記帳法常用的原因 04/28 13:11
※ 編輯: kronze7109 (42.77.46.4 臺灣), 04/28/2021 21:50:01
推 aa871220: 我覺得立宇這個解法有點難懂 04/28 23:16
→ aa871220: 這題是CLRS的習題 你可以找一下amortized cost那章的解 04/28 23:16
→ aa871220: 答 我覺得寫得比較好 04/28 23:16
→ aa871220: （有點懶就懶得貼了sorry) 04/28 23:16
謝謝a大
我會找時間去看CLRS的！！
推 kaneson: potential function 其實只要不違背前提可自由發揮, 只是 04/29 09:55
→ kaneson: 得到的cost是否夠tight, 課本的stack例子二種做法都有點 04/29 09:55
→ kaneson: 像是不違反前提下把某些操作cost挪給別的操作來保持tight 04/29 09:55
推 kaneson: 這題可用tree node深度加總來當位能, 每個 node 平均深 04/29 09:59
→ kaneson: 度lgn, 增加一個node就總和增加lgn, 少一個node就少lgn. 04/29 09:59
→ kaneson: 用這個來做位能差。網路上有解法是寫lg1加到lgn就結束了 04/29 09:59
謝謝k大
後面的計算我有理解出增減一個node都為lgn的cost
但不理解他potential function裡面符號的定義
→ kaneson: ,林的寫法是在數學上比較嚴謹 04/29 09:59
※ 編輯: kronze7109 (42.77.46.4 臺灣), 04/29/2021 12:52:40
※ 編輯: kronze7109 (42.77.46.4 臺灣), 04/29/2021 12:54:05
推 NTUmaki: 去看台大演算法影片教比較清楚 04/30 13:23