[理工] 交大104資演

看板Grad-ProbAsk作者時間6年前 (2019/12/31 15:31), 編輯推噓3(3推 0噓 7→)
留言10則, 5人參與, 6年前最新討論串1/1
http://i.imgur.com/pOyUln0.jpg
請問這題234 2要怎麼算 3不知道在考什麽觀念QQ 4符合optimal substructure property 不能保證global optimal 嗎OAO?為甚麼 http://i.imgur.com/3Z3IuCp.jpg
38題 想問到底怎麼算，只知道merge兩組會是O((n/k)log(n/k))再多就卡住了QQ ----- Sent from JPTT on my Samsung SM-N960F. -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 114.136.62.164 (臺灣) ※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1577777477.A.D5B.html
→
12/31 15:37, 6年前 , 1F
2是ceiling(log(6!))
12/31 15:37, 1F
→
12/31 15:38, 6年前 , 2F
3在立宇老師的講義2-4最後面
12/31 15:38, 2F
→
12/31 15:39, 6年前 , 3F
4是錯後面那句話local 必然可以保證global 是錯的
12/31 15:39, 3F
推
12/31 15:57, 6年前 , 4F
merge 2組長度分別為m, n的sorted list複雜度是O(m+n)
12/31 15:57, 4F
→
12/31 15:57, 6年前 , 5F
不是你寫的那個
12/31 15:57, 5F
→
12/31 17:11, 6年前 , 6F
最後一次是(k-1)n/k+n/k=n，共執行k次
12/31 17:11, 6F
推
12/31 18:13, 6年前 , 7F
4global最佳解是由local拼湊的，並不是local最佳直
12/31 18:13, 7F
→
12/31 18:13, 6年前 , 8F
接=global 最佳
12/31 18:13, 8F
推
12/31 21:08, 6年前 , 9F
3就是median of medians,然後考的觀念是3個一群跟5個一群的
12/31 21:08, 9F
→
12/31 21:08, 6年前 , 10F
複雜度會不一樣
12/31 21:08, 10F
‣ 更多 janet0305 的文章
文章代碼(AID): #1U2lb5rR (Grad-ProbAsk)