作者gash55025502 (白影弓)
看板Grad-ProbAsk
標題[理工] 107台大資演
時間Wed Dec 11 12:46:06 2019
https://i.imgur.com/gXSnfrP.jpg
大家好 想問一下這題的第二小題
我知道accounting method的方法
課本上的例子是讓enquece的cost設2 dequeue設0
但這題因為有特別說是用stack implement的queue
感覺應該不能用上面的寫法
請問有人知道這題應該怎麼寫嗎？
或者能要一下立宇老師的題庫班講義這題的寫法嗎？感謝～
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 140.117.248.5 (臺灣)
※ 文章網址: https://webptt.com/m.aspx?n=bbs/Grad-ProbAsk/M.1576039568.A.C49.html
1F：推 mistel: 把enqueue設3 其中有1是push進stack 1，另外1是pop後push 12/11 13:11
2F：→ mistel: 進stack 2的成本，第三個1是從stack 2 pop的成本，所以這 12/11 13:11
3F：→ mistel: 樣也可以分攤成enqueue O(n)，Dequeue 0 不知道對不對... 12/11 13:11
4F：推 mistel: 覺得基本想法還是dequeue成本不會超過enqueue 然後把成本 12/11 13:15
5F：→ mistel: 定在每個元素的push和pop，但我才剛學amortized analysis 12/11 13:15
6F：→ mistel: ，講錯請鞭小力點qq 12/11 13:15
7F：→ gash55025502: 感覺蠻有道理的！感謝 12/11 20:16