[理工] 台大 107 資演

[jimmy1112111 (jxu)]

 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://www.ptt.cc/bbs/Grad-ProbAsk/M.1640186790.A.AF6.html
推 BusterButter: 用這個potential function的話, 當你其中一個stack
→ BusterButter: 是空的時候，你做pop的 還會是O(1)嗎
→ BusterButter: 用3個stack的話deque可以達到amortized O(1)，但是
→ BusterButter: 只有兩個的話我就不確定了，我覺得這題感覺是不行
→ jimmy1112111: 謝謝，我再研究看看