[理工] 104台大電機 資演

看板Grad-ProbAsk作者 (揪立)時間9年前 (2017/01/20 01:50), 編輯推噓5(5推 0噓 9→)
留言14則, 4人參與, 最新討論串1/1
http://i.imgur.com/MwWDra5.jpg
第六題爬文一下 有人說可以用DFS解決 為什麼呢QQ http://i.imgur.com/pmEy7C7.jpg
這個A選項是在說明什麼呢，看不太懂想問蝦米QQ http://i.imgur.com/ZZNtwCZ.jpg
藍筆的三個選項 其中16D為什麼是exponential呀？應該不可能那麼多吧？ 剩下兩個有勞大大幫忙解答，謝謝 -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 42.73.91.184 ※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1484848230.A.C31.html
推
01/20 07:45, , 1F
1，拓樸排序
01/20 07:45, 1F
推
01/20 15:14, , 2F
我也有疑問QQ
01/20 15:14, 2F
推
01/20 17:17, , 3F
16. (D) 應該是錯的 用DFS就可解
01/20 17:17, 3F
→
01/20 17:22, , 4F
goo.gl/jbEave
01/20 17:22, 4F
→
01/20 17:23, , 5F
16.(E) 可以參考這個 goo.gl/LnvEPY
01/20 17:23, 5F
推
01/20 22:01, , 6F
15 一個 tree 第 k 層有 k + 2 個子節點
01/20 22:01, 6F
→
01/20 22:02, , 7F
這很明顯的比二元樹要多很多節點 所以節點數不是O(2^n)
01/20 22:02, 7F
推
01/20 22:06, , 8F
15 如果有 n = 2^h - 1 個節點 那麼 minimum tree height
01/20 22:06, 8F
→
01/20 22:06, , 9F
的樹只有一種可能（完全平衡） 但是 n 節點的二元樹有指數
01/20 22:06, 9F
→
01/20 22:07, , 10F
種 所以機率應該非常小
01/20 22:07, 10F
→
01/20 22:08, , 11F
16 D 如果 DAG 是一串菱形 起點到終點就有指數種路徑
01/20 22:08, 11F
→
01/20 22:09, , 12F
16 E 最大 degree d -> 最大 clique size d + 1
01/20 22:09, 12F
→
01/20 22:10, , 13F
因為最大 clique size 是 d+1 要 cover n 點就要 n/(d+1)
01/20 22:10, 13F
→
01/20 22:10, , 14F
個 clique
01/20 22:10, 14F
‣ 更多 joeboy 的文章
文章代碼(AID): #1OWFncmn (Grad-ProbAsk)