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

看板Grad-ProbAsk作者 (Kobe Mary)時間4年前 (2019/12/18 11:39), 編輯推噓3(3推 0噓 25→)
留言28則, 5人參與, 4年前最新討論串1/1
請大大指導下面幾題 謝謝 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
→
12/18 12:09, 4年前 , 1F
hash table不夠大的時候就重新建一個 然後全部重放這樣
12/18 12:09, 1F
→
12/18 12:11, 4年前 , 2F
weight都正的dijkstra下去做就好了吧
12/18 12:11, 2F
→
12/18 13:07, 4年前 , 3F
第4題 直接生mst就好了 用dfs表示順序就好
12/18 13:07, 3F
→
12/18 14:31, 4年前 , 4F
最上面是說一次比較可以區分出兩種排列a>b or a<b.問若
12/18 14:31, 4F
→
12/18 14:31, 4年前 , 5F
有k次比較有幾種排列方法，主要考的是log(n!)
12/18 14:31, 5F
→
12/18 16:31, 4年前 , 6F
D大 所以hash那題為TTF? 只是dijkstra會要開一個很大的
12/18 16:31, 6F
→
12/18 16:31, 4年前 , 7F
表格 有點抖 怕他考的不是這個
12/18 16:31, 7F
→
12/18 16:32, 4年前 , 8F
z大 第四題是要做shortest path吧？
12/18 16:32, 8F
→
12/18 16:36, 4年前 , 9F
r大 看沒有很懂。decision tree的每一層 不就代表一次
12/18 16:36, 9F
→
12/18 16:36, 4年前 , 10F
比較 k次comparison 是指有k層？
12/18 16:36, 10F
推
12/18 17:08, 4年前 , 11F
Shotrtest path spanning tree 不就mst 換個名字
12/18 17:08, 11F
→
12/18 17:13, 4年前 , 12F
12/18 17:13, 12F
→
12/18 19:33, 4年前 , 13F
z大 shortest path spanning tree應該是做dijkstra然後
12/18 19:33, 13F
→
12/18 19:33, 4年前 , 14F
把它畫成tree吧？MST與shortest path應該沒關係？
12/18 19:33, 14F
→
12/18 19:36, 4年前 , 15F
我知道他在考筆記這段觀念 我想我可能是卡在k compariso
12/18 19:36, 15F
→
12/18 19:36, 4年前 , 16F
n 所以沒辦法把筆記與題目連接上
12/18 19:36, 16F
→
12/18 19:36, 4年前 , 17F
有比較好的k comaparison的解釋？
12/18 19:36, 17F
推
12/18 19:59, 4年前 , 18F
d大說惹，直接用Dijkstra's去跑就好了
12/18 19:59, 18F
推
12/18 20:03, 4年前 , 19F
第一題的話，兩個element a,b，可以經過比較“1”次後找
12/18 20:03, 19F
→
12/18 20:03, 4年前 , 20F
到a,b或b,a兩種可能 所以k次比較可以找到(k+1)!種排序結
12/18 20:03, 20F
→
12/18 20:03, 4年前 , 21F
果，就像z大貼的筆記所寫的，就是決策樹從root到達leaf（
12/18 20:03, 21F
→
12/18 20:03, 4年前 , 22F
結果）至多要經過多少比較，而這題只是反過來問你而已
12/18 20:03, 22F
→
12/19 00:26, 4年前 , 23F
c應該是T喔 普遍會要一個原本兩倍大小的hash table
12/19 00:26, 23F
→
12/19 12:52, 4年前 , 24F
謝謝m大 z大 我好像懂了
12/19 12:52, 24F
→
12/19 12:54, 4年前 , 25F
D大 這是用hash的經驗法則？太小才不會過多的collision
12/19 12:54, 25F
→
12/19 12:54, 4年前 , 26F
太大浪費空間的意思？
12/19 12:54, 26F
→
12/19 15:11, 4年前 , 27F
我對hash沒什麼研究欸 2倍的由來我也不確定 應該是這樣XD
12/19 15:11, 27F
→
12/21 22:41, 4年前 , 28F
D大 謝謝你！
12/21 22:41, 28F
‣ 更多 dsa66253 的文章
文章代碼(AID): #1T-Pz_Li (Grad-ProbAsk)