[理工] 104 105交大資演幾題

看板Grad-ProbAsk作者 (chunk)時間5年前 (2019/01/18 11:14), 編輯推噓3(3推 0噓 13→)
留言16則, 4人參與, 5年前最新討論串1/1
32.https://imgur.com/a/Lo3vkkN 首先104的32題的第二個選項 這種給固定數量elements要做幾次comparison需要怎麼算呢 24.https://imgur.com/a/hDjk67A 105的24題的(c)(d)選項 雖然說這題之前有蠻多人討論過了 但是仍然很不理解為什麼(d)說用non-linear可以突破 nlogn 不是一定要linear sorting才能辦得到嗎？ 然後(c)主要是不知道decision tree前面加一個linear是什麼意思 48.https://imgur.com/a/sXQfB3g 48題的(c)選項 怎麼看到林立宇講義上面105頁是寫說用binary heap單步驟進行decrease key 的確是 logV 的時間啊？ 還是我的觀念有錯嗎？ 謝謝大家幫解惑^^ -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 140.113.136.218 ※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1547781257.A.75C.html
→
01/18 11:48, 5年前 , 1F
第一題decision tree解 你上面不就有寫了
01/18 11:48, 1F
推
01/18 11:56, 5年前 , 2F
48(c) log V 應該沒錯
01/18 11:56, 2F
→
01/18 11:56, 5年前 , 3F
24 題比較難
01/18 11:56, 3F
→
01/18 11:57, 5年前 , 4F
一般的 sorting lower bound 是用 comparison 證明的
01/18 11:57, 4F
→
01/18 11:57, 5年前 , 5F
但是 linear decision tree model 也可以證明
01/18 11:57, 5F
推
01/18 12:03, 5年前 , 6F
01/18 12:03, 6F
→
01/18 12:05, 5年前 , 7F
所以 24 (c) 要看你怎麼解釋
01/18 12:05, 7F
→
01/18 12:05, 5年前 , 8F
linear decision tree 的 lower bound 會 imply
01/18 12:05, 8F
→
01/18 12:06, 5年前 , 9F
comparison model 的 lower bound
01/18 12:06, 9F
→
01/18 12:06, 5年前 , 10F
但是大部分課本上都是只證明 comparison model 的..
01/18 12:06, 10F
→
01/18 12:07, 5年前 , 11F
24 (d) 的話 因為 non-linear 可能會提供 extra power
01/18 12:07, 11F
→
01/18 12:07, 5年前 , 12F
所以有可能可以 beat O(n lg n)
01/18 12:07, 12F
→
01/18 13:57, 5年前 , 13F
回水餃大大是的，但是不知道這樣是不是對的
01/18 13:57, 13F
→
01/18 13:59, 5年前 , 14F
因為那個應該是ave. case，但是題目是問worst case
01/18 13:59, 14F
→
01/18 16:41, 5年前 , 15F
謝謝F大這麼詳盡的講解
01/18 16:41, 15F
推
01/18 16:48, 5年前 , 16F
說個題外話 你知道貼圖片不是複製那個網址嗎
01/18 16:48, 16F
‣ 更多 leekevinming 的文章
文章代碼(AID): #1SGKI9TS (Grad-ProbAsk)