[理工][演算法]-台大105-資工

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