[理工] [DS]103 台大資工 對答案+問題

看板Grad-ProbAsk作者 (winnie)時間11年前 (2015/01/24 16:21), 編輯推噓9(9推 0噓 9→)
留言18則, 8人參與, 最新討論串1/3 (看更多)
先附上題目連結： http://exam.lib.ntu.edu.tw/sites/default/files/exam/graduate/103/103424.pdf 就快要考試了，卻還是都找不到這份的相關討論，所以就po上自己寫的和大家討論！不過 這年的感覺有點難，有些不會的題目希望大家能給點提示~有錯誤的歡迎指正！ 不會寫的題目有： 1(b) 這感覺蠻基本...、3(c)、4 謝謝！大家加油！ http://i.imgur.com/gPRLRxT.jpg
http://i.imgur.com/VfrkNFE.jpg
http://i.imgur.com/d56ynn5.jpg
-- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 115.43.67.205 ※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1422087695.A.ACA.html
推
01/24 17:59, , 1F
這份真的爆難...
01/24 17:59, 1F
推
01/24 19:10, , 2F
1(a)應該是lognloglogn,展開應該是loglogn項
01/24 19:10, 2F
→
01/24 19:10, , 3F
1(b)我是用Substitution method猜O(n)去證
01/24 19:10, 3F
→
01/24 19:12, , 4F
2(b)我算degree最大=logn,發生在root
01/24 19:12, 4F
→
01/24 19:14, , 5F
4我戰友做法是先作topological sort之後再ＤＰ
01/24 19:14, 5F
→
01/24 19:20, , 6F
這份我想問2(a)跟5(c)要怎麼做
01/24 19:20, 6F
→
01/24 19:38, , 7F
3(c)把HP reduce成max degree=2的spanning tree問題
01/24 19:38, 7F
推
01/24 23:02, , 8F
01/24 23:02, 8F
→
01/24 23:02, , 9F
4如果用DP作應該不是polynomial time 但是應該是答案
01/24 23:02, 9F
推
01/24 23:33, , 10F
爆難+1
01/24 23:33, 10F
→
01/25 08:23, , 11F
謝謝大家提供的方法!晚點來研究!
01/25 08:23, 11F
推
01/25 09:49, , 12F
早上起來突然想到1（b）應該可以用遞洄樹去看
01/25 09:49, 12F
推
01/25 09:55, , 13F
1(b)應該可以只看n/2這項? 根號n n變大時衰減很快
01/25 09:55, 13F
→
01/25 10:15, , 14F
對阿，一開始我也是那樣想，不過今天想想好像用遞迴樹會
01/25 10:15, 14F
→
01/25 10:15, , 15F
更好。
01/25 10:15, 15F
推
01/25 12:58, , 16F
Thx f大
01/25 12:58, 16F
推
02/01 01:03, , 17F
4 用暴力法找出每條路O(n^2)就能解
02/01 01:03, 17F
推
01/28 12:36, , 18F
1.B 洪毅在解時說約等於T(n/2)+n
01/28 12:36, 18F
‣ 更多 winnie48 的文章
文章代碼(AID): #1KmrOFhA (Grad-ProbAsk)
討論串 (同標題文章)
以下文章回應了本文 (最舊先)：
完整討論串 (本文為第 1 之 3 篇)：
排序： 最新先 | 最舊先 | 留言數
在新視窗開啟完整討論串 (共3篇)
‣ 更多 winnie48 的文章
文章代碼(AID): #1KmrOFhA (Grad-ProbAsk)