作者leekevinming (chunk)
看板Grad-ProbAsk
标题[理工] 104 105交大资演几题
时间Fri Jan 18 11:14:15 2019
32.
https://imgur.com/a/Lo3vkkN
首先104的32题的第二个选项
这种给固定数量elements要做几次comparison需要怎麽算呢
24.
https://imgur.com/a/hDjk67A
105的24题的(c)(d)选项
虽然说这题之前有蛮多人讨论过了
但是仍然很不理解为什麽(d)说用non-linear可以突破 nlogn
不是一定要linear sorting才能办得到吗？
然後(c)主要是不知道decision tree前面加一个linear是什麽意思
48.
https://imgur.com/a/sXQfB3g
48题的(c)选项
怎麽看到林立宇讲义上面105页是写说用binary heap单步骤进行decrease key
的确是 logV 的时间啊？
还是我的观念有错吗？
谢谢大家帮解惑^^
--
※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 140.113.136.218
※ 文章网址: https://webptt.com/cn.aspx?n=bbs/Grad-ProbAsk/M.1547781257.A.75C.html
1F：→ dumpling1234: 第一题decision tree解 你上面不就有写了 01/18 11:48
2F：推 FRAXIS: 48(c) log V 应该没错 01/18 11:56
3F：→ FRAXIS: 24 题比较难 01/18 11:56
4F：→ FRAXIS: 一般的 sorting lower bound 是用 comparison 证明的 01/18 11:57
5F：→ FRAXIS: 但是 linear decision tree model 也可以证明 01/18 11:57
7F：→ FRAXIS: 所以 24 (c) 要看你怎麽解释 01/18 12:05
8F：→ FRAXIS: linear decision tree 的 lower bound 会 imply 01/18 12:05
9F：→ FRAXIS: comparison model 的 lower bound 01/18 12:06
10F：→ FRAXIS: 但是大部分课本上都是只证明 comparison model 的.. 01/18 12:06
11F：→ FRAXIS: 24 (d) 的话 因为 non-linear 可能会提供 extra power 01/18 12:07
12F：→ FRAXIS: 所以有可能可以 beat O(n lg n) 01/18 12:07
13F：→ leekevinming: 回水饺大大是的，但是不知道这样是不是对的 01/18 13:57
14F：→ leekevinming: 因为那个应该是ave. case，但是题目是问worst case 01/18 13:59
15F：→ leekevinming: 谢谢F大这麽详尽的讲解 01/18 16:41
16F：推 imadog: 说个题外话 你知道贴图片不是复制那个网址吗 01/18 16:48