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