[理工] 107台大資演

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