作者kronze7109 (Kronze)
看板Grad-ProbAsk
標題［理工］105台大演算法
時間Tue Apr 27 23:42:05 2021
強者大大，大家好
小弟第一次發文
排版混亂麻煩大家多擔待
想請問
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
先叩謝各位大大了
-----
Sent from JPTT on my Google Pixel 4.
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 42.77.46.4 (臺灣)
※ 文章網址: https://webptt.com/m.aspx?n=bbs/Grad-ProbAsk/M.1619538127.A.A6B.html
1F：推 kaneson: 位能法當於對毎個操作設計如何改變某個全域變數的量，可 04/28 12:25
2F：→ kaneson: 以有加有減，然後檢查連續n個任意操作過程中這個值都不會 04/28 12:25
3F：→ kaneson: 比起始低，就是個ok的設計。此時 平攤cost=原cost + 你設 04/28 12:25
4F：→ kaneson: 計的位能變化 04/28 12:25
5F：推 kaneson: 然後這個位能值通常做法是跟你要操作的資料結構用個funct 04/28 13:10
6F：→ kaneson: ion對應成一個值，這樣就很容易驗證是否滿足前提. 而相 04/28 13:11
謝謝解釋，原理懂了
但還是無法理解解答那個potential function的為何是那樣QQ
7F：→ kaneson: 對記帳法，設計時只需對每個操作綁一個固定值，乍看很簡 04/28 13:11
8F：→ kaneson: 單，但若要驗證過程中會不會發生總和低於0就比較麻煩。這 04/28 13:11
9F：→ kaneson: 就是位能法比記帳法常用的原因 04/28 13:11
※ 編輯: kronze7109 (42.77.46.4 臺灣), 04/28/2021 21:50:01
10F：推 aa871220: 我覺得立宇這個解法有點難懂 04/28 23:16
11F：→ aa871220: 這題是CLRS的習題 你可以找一下amortized cost那章的解 04/28 23:16
12F：→ aa871220: 答 我覺得寫得比較好 04/28 23:16
13F：→ aa871220: （有點懶就懶得貼了sorry) 04/28 23:16
謝謝a大
我會找時間去看CLRS的！！
14F：推 kaneson: potential function 其實只要不違背前提可自由發揮, 只是 04/29 09:55
15F：→ kaneson: 得到的cost是否夠tight, 課本的stack例子二種做法都有點 04/29 09:55
16F：→ kaneson: 像是不違反前提下把某些操作cost挪給別的操作來保持tight 04/29 09:55
17F：推 kaneson: 這題可用tree node深度加總來當位能, 每個 node 平均深 04/29 09:59
18F：→ kaneson: 度lgn, 增加一個node就總和增加lgn, 少一個node就少lgn. 04/29 09:59
19F：→ kaneson: 用這個來做位能差。網路上有解法是寫lg1加到lgn就結束了 04/29 09:59
謝謝k大
後面的計算我有理解出增減一個node都為lgn的cost
但不理解他potential function裡面符號的定義
20F：→ 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
21F：推 NTUmaki: 去看台大演算法影片教比較清楚 04/30 13:23