作者janet0305 ()
看板Grad-ProbAsk
標題[理工] 交大104資演
時間Tue Dec 31 15:31:15 2019
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://webptt.com/m.aspx?n=bbs/Grad-ProbAsk/M.1577777477.A.D5B.html
1F：→ bochengchen: 2是ceiling(log(6!)) 12/31 15:37
2F：→ bochengchen: 3在立宇老師的講義2-4最後面 12/31 15:38
3F：→ bochengchen: 4是錯後面那句話local 必然可以保證global 是錯的 12/31 15:39
4F：推 mi981027: merge 2組長度分別為m, n的sorted list複雜度是O(m+n) 12/31 15:57
5F：→ mi981027: 不是你寫的那個 12/31 15:57
6F：→ b10007034: 最後一次是(k-1)n/k+n/k=n，共執行k次 12/31 17:11
7F：推 cry589036511: 4global最佳解是由local拼湊的，並不是local最佳直 12/31 18:13
8F：→ cry589036511: 接=global 最佳 12/31 18:13
9F：推 Kedge: 3就是median of medians,然後考的觀念是3個一群跟5個一群的 12/31 21:08
10F：→ Kedge: 複雜度會不一樣 12/31 21:08