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

[leekevinming (chunk)]

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
→ dumpling1234: 第一題decision tree解 你上面不就有寫了
推 FRAXIS: 48(c) log V 應該沒錯
→ FRAXIS: 24 題比較難
→ FRAXIS: 一般的 sorting lower bound 是用 comparison 證明的
→ FRAXIS: 但是 linear decision tree model 也可以證明
推 FRAXIS: https://algs4.cs.princeton.edu/65reductions/
→ FRAXIS: 所以 24 (c) 要看你怎麼解釋
→ FRAXIS: linear decision tree 的 lower bound 會 imply
→ FRAXIS: comparison model 的 lower bound
→ FRAXIS: 但是大部分課本上都是只證明 comparison model 的..
→ FRAXIS: 24 (d) 的話 因為 non-linear 可能會提供 extra power
→ FRAXIS: 所以有可能可以 beat O(n lg n)
→ leekevinming: 回水餃大大是的，但是不知道這樣是不是對的
→ leekevinming: 因為那個應該是ave. case，但是題目是問worst case
→ leekevinming: 謝謝F大這麼詳盡的講解
推 imadog: 說個題外話 你知道貼圖片不是複製那個網址嗎