作者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/cn.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