作者mistel (Mistel)
看板Grad-ProbAsk
标题[理工] 107 电机丙 资结 几题问题
时间Tue Dec 24 16:24:20 2019
https://webptt.com/cn.aspx?n=bbs/Grad-ProbAsk/M.1548751851.A.8FB.html
可参考前人的文章有一些讨论
附上对来的答案：
https://i.imgur.com/gyvk583.jpg
请问
https://i.imgur.com/zJ5xLqG.jpg
第4题要keep track中位数就只能用递回的那个演算法吗？
https://i.imgur.com/Gy4b0nR.jpg
请问第八题的t()是怎麽维持的？看不懂之前的文章
https://i.imgur.com/0ONY1uc.jpg
请问这题a选项为什麽错？
感谢大家
--
※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 114.136.184.208 (台湾)
※ 文章网址: https://webptt.com/cn.aspx?n=bbs/Grad-ProbAsk/M.1577175862.A.BAC.html
1F：推 jeremyyuan: 4 我也写false median用augmented AVL不是可以到logn12/24 16:36
2F：→ jeremyyuan: 吗 甚至直接用一个指标指 1by1给不就O(1)? 16E应该错12/24 16:36
3F：→ jeremyyuan: 的 splay会斜取 19我也有选a12/24 16:36
splay分摊时间应该是logn？ 洪逸的笔记这样写的
※ 编辑: mistel (114.136.184.208 台湾), 12/24/2019 16:54:30
4F：→ mistel: 不过真要说heap的delete也可以分摊到O(1)，所以有时候真 12/24 16:55
5F：→ mistel: 不知道台大到底该答什麽... 12/24 16:55
6F：→ jeremyyuan: worst case是O(n) 12/24 16:56
7F：→ mistel: 我看到了 感谢你 12/24 16:58
8F：→ jeremyyuan: 没事 worst case也要用amortized 是我错了 12/24 17:01
10F：→ jeremyyuan: 不过感觉怪怪的 worst是O(n)然後又amortized ... 12/24 17:15
11F：→ mistel: 我看其他网站写O(n) worst case，不知道圣经本写什麽：（ 12/25 12:14
12F：→ jeremyyuan: 我看题库班 洪逸也是写ABCD worst case 还是O(n)啦 12/25 12:43
13F：→ jeremyyuan: 但维基把他amortized了= = 12/25 12:43