作者dsa66253 (Kobe Mary)
看板Grad-ProbAsk
标题[理工] 101台大资演 1-2 4-2
时间Wed Dec 18 11:39:41 2019
请大大指导下面几题 谢谢
https://i.imgur.com/s82jxEv.jpg
请问第二小题这是什麽意思？ 是一次可以比k个element? 我看人家答案写k+1阶乘
https://i.imgur.com/X1QTS9H.jpg
请问第二小题这个ac是什麽意思？
https://i.imgur.com/SbqNTW2.jpg
这个第四小题，真的只有开一个16*16的表格硬着头皮做？
--
※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 150.117.242.146 (台湾)
※ 文章网址: https://webptt.com/cn.aspx?n=bbs/Grad-ProbAsk/M.1576640383.A.56C.html
1F：→ DLHZ: hash table不够大的时候就重新建一个 然後全部重放这样 12/18 12:09
2F：→ DLHZ: weight都正的dijkstra下去做就好了吧 12/18 12:11
3F：→ zuchang: 第4题 直接生mst就好了 用dfs表示顺序就好 12/18 13:07
4F：→ rayroyray: 最上面是说一次比较可以区分出两种排列a>b or a<b.问若 12/18 14:31
5F：→ rayroyray: 有k次比较有几种排列方法，主要考的是log(n!) 12/18 14:31
6F：→ dsa66253: D大 所以hash那题为TTF? 只是dijkstra会要开一个很大的 12/18 16:31
7F：→ dsa66253: 表格 有点抖 怕他考的不是这个 12/18 16:31
8F：→ dsa66253: z大 第四题是要做shortest path吧？ 12/18 16:32
9F：→ dsa66253: r大 看没有很懂。decision tree的每一层 不就代表一次 12/18 16:36
10F：→ dsa66253: 比较 k次comparison 是指有k层？ 12/18 16:36
11F：推 zuchang: Shotrtest path spanning tree 不就mst 换个名字 12/18 17:08
13F：→ dsa66253: z大 shortest path spanning tree应该是做dijkstra然後 12/18 19:33
14F：→ dsa66253: 把它画成tree吧？MST与shortest path应该没关系？ 12/18 19:33
15F：→ dsa66253: 我知道他在考笔记这段观念 我想我可能是卡在k compariso 12/18 19:36
16F：→ dsa66253: n 所以没办法把笔记与题目连接上 12/18 19:36
17F：→ dsa66253: 有比较好的k comaparison的解释？ 12/18 19:36
18F：推 mistel: d大说惹，直接用Dijkstra's去跑就好了 12/18 19:59
19F：推 mistel: 第一题的话，两个element a,b，可以经过比较“1”次後找 12/18 20:03
20F：→ mistel: 到a,b或b,a两种可能 所以k次比较可以找到(k+1)!种排序结 12/18 20:03
21F：→ mistel: 果，就像z大贴的笔记所写的，就是决策树从root到达leaf（ 12/18 20:03
22F：→ mistel: 结果）至多要经过多少比较，而这题只是反过来问你而已 12/18 20:03
23F：→ DLHZ: c应该是T喔 普遍会要一个原本两倍大小的hash table 12/19 00:26
24F：→ dsa66253: 谢谢m大 z大 我好像懂了 12/19 12:52
25F：→ dsa66253: D大 这是用hash的经验法则？太小才不会过多的collision 12/19 12:54
26F：→ dsa66253: 太大浪费空间的意思？ 12/19 12:54
27F：→ DLHZ: 我对hash没什麽研究欸 2倍的由来我也不确定 应该是这样XD 12/19 15:11
28F：→ dsa66253: D大 谢谢你！ 12/21 22:41