[理工] 台大 107 資演
想問(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
推
12/23 01:11,
4年前
, 1F
12/23 01:11, 1F
→
12/23 01:11,
4年前
, 2F
12/23 01:11, 2F
→
12/23 01:13,
4年前
, 3F
12/23 01:13, 3F
→
12/23 01:13,
4年前
, 4F
12/23 01:13, 4F
→
12/23 10:47,
4年前
, 5F
12/23 10:47, 5F