作者jimmy1112111 (jxu)
看板Grad-ProbAsk
標題[理工] 台大 107 資演
時間Wed Dec 22 23:26:28 2021
https://i.imgur.com/2FoQuIC.jpg
想問(b)的第三小題
假設deque是用兩個stack implement，使用potential method證明，令potential function
為兩個stack的total element數，
把四個operation(push_front, push_back, pop_front, pop_back)列出來，c head皆為O(1
)，因此n個operations是O(n)，因此amortized time是O(n)
不知這樣證明是否可行？
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 113.61.200.52 (臺灣)
※ 文章網址: https://webptt.com/m.aspx?n=bbs/Grad-ProbAsk/M.1640186790.A.AF6.html
1F：推 BusterButter: 用這個potential function的話, 當你其中一個stack 12/23 01:11
2F：→ BusterButter: 是空的時候，你做pop的 還會是O(1)嗎 12/23 01:11
3F：→ BusterButter: 用3個stack的話deque可以達到amortized O(1)，但是 12/23 01:13
4F：→ BusterButter: 只有兩個的話我就不確定了，我覺得這題感覺是不行 12/23 01:13
5F：→ jimmy1112111: 謝謝，我再研究看看 12/23 10:47