作者gj94jo3a12 (NTUWayne)
看板Grad-ProbAsk
标题[理工] 109台大电信资演两题
时间Sat Jan 16 15:07:41 2021
1.
https://i.imgur.com/qS6Luo4.jpg
Splay tree 的worst case为O(n) Amortized cost为O(logn)
所以B D选项是O(n)还是O(logn)？
这题的答案又是什麽呢？
2.
https://i.imgur.com/LS7nYzH.jpg
https://i.imgur.com/dc0EZGv.jpg
Fib heap的操作 不是很确定 我写AD
其中AB选项我是这样写有错请指正
https://i.imgur.com/gUp2NM2.jpg
手机排版 很乱抱歉
--
※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 42.77.146.10 (台湾)
※ 文章网址: https://webptt.com/cn.aspx?n=bbs/Grad-ProbAsk/M.1610780863.A.FAD.html
※ 编辑: gj94jo3a12 (42.77.146.10 台湾), 01/16/2021 15:08:46
1F：推 kopk159: 2.b 59->40 树没变化吧 01/16 19:14
2F：推 joywilliamjo: 他worat case amortized cost也是O(logn)啊，我觉得 01/16 19:40
3F：→ joywilliamjo: 1 BD都对欸 01/16 19:40
4F：→ gj94jo3a12: 2b 没变化才对 感谢提醒 01/16 19:53
5F：→ gj94jo3a12: 所以才不确定1.是要用单一worst case O(n)还是amortiz 01/16 19:54
6F：→ gj94jo3a12: ed costO(logn) 01/16 19:54
7F：推 asd597326: 借问 所以台大的splay都要考虑amortized case吗 01/20 15:37