[理工] 101台大資演 1-2 4-2

[dsa66253 (Kobe Mary)]

請大大指導下面幾題 謝謝

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://www.ptt.cc/bbs/Grad-ProbAsk/M.1576640383.A.56C.html
→ DLHZ: hash table不夠大的時候就重新建一個 然後全部重放這樣
→ DLHZ: weight都正的dijkstra下去做就好了吧
→ zuchang: 第4題 直接生mst就好了 用dfs表示順序就好
→ rayroyray: 最上面是說一次比較可以區分出兩種排列a>b or a<b.問若
→ rayroyray: 有k次比較有幾種排列方法，主要考的是log(n!)
→ dsa66253: D大 所以hash那題為TTF? 只是dijkstra會要開一個很大的
→ dsa66253: 表格 有點抖 怕他考的不是這個
→ dsa66253: z大 第四題是要做shortest path吧？
→ dsa66253: r大 看沒有很懂。decision tree的每一層 不就代表一次
→ dsa66253: 比較 k次comparison 是指有k層？
推 zuchang: Shotrtest path spanning tree 不就mst 換個名字
→ zuchang: https://i.imgur.com/oP0QRzj.jpg
→ dsa66253: z大 shortest path spanning tree應該是做dijkstra然後
→ dsa66253: 把它畫成tree吧？MST與shortest path應該沒關係？
→ dsa66253: 我知道他在考筆記這段觀念 我想我可能是卡在k compariso
→ dsa66253: n 所以沒辦法把筆記與題目連接上
→ dsa66253: 有比較好的k comaparison的解釋？
推 mistel: d大說惹，直接用Dijkstra's去跑就好了
推 mistel: 第一題的話，兩個element a,b，可以經過比較“1”次後找
→ mistel: 到a,b或b,a兩種可能 所以k次比較可以找到(k+1)!種排序結
→ mistel: 果，就像z大貼的筆記所寫的，就是決策樹從root到達leaf（
→ mistel: 結果）至多要經過多少比較，而這題只是反過來問你而已
→ DLHZ: c應該是T喔 普遍會要一個原本兩倍大小的hash table
→ dsa66253: 謝謝m大 z大 我好像懂了
→ dsa66253: D大 這是用hash的經驗法則？太小才不會過多的collision
→ dsa66253:  太大浪費空間的意思？
→ DLHZ: 我對hash沒什麼研究欸 2倍的由來我也不確定 應該是這樣XD
→ dsa66253: D大 謝謝你！