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