作者leekevinming (chunk)
看板Grad-ProbAsk
標題[理工] 104 105交大資演幾題
時間Fri Jan 18 11:14:15 2019
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://webptt.com/m.aspx?n=bbs/Grad-ProbAsk/M.1547781257.A.75C.html
1F：→ dumpling1234: 第一題decision tree解 你上面不就有寫了 01/18 11:48
2F：推 FRAXIS: 48(c) log V 應該沒錯 01/18 11:56
3F：→ FRAXIS: 24 題比較難 01/18 11:56
4F：→ FRAXIS: 一般的 sorting lower bound 是用 comparison 證明的 01/18 11:57
5F：→ FRAXIS: 但是 linear decision tree model 也可以證明 01/18 11:57
7F：→ FRAXIS: 所以 24 (c) 要看你怎麼解釋 01/18 12:05
8F：→ FRAXIS: linear decision tree 的 lower bound 會 imply 01/18 12:05
9F：→ FRAXIS: comparison model 的 lower bound 01/18 12:06
10F：→ FRAXIS: 但是大部分課本上都是只證明 comparison model 的.. 01/18 12:06
11F：→ FRAXIS: 24 (d) 的話 因為 non-linear 可能會提供 extra power 01/18 12:07
12F：→ FRAXIS: 所以有可能可以 beat O(n lg n) 01/18 12:07
13F：→ leekevinming: 回水餃大大是的，但是不知道這樣是不是對的 01/18 13:57
14F：→ leekevinming: 因為那個應該是ave. case，但是題目是問worst case 01/18 13:59
15F：→ leekevinming: 謝謝F大這麼詳盡的講解 01/18 16:41
16F：推 imadog: 說個題外話 你知道貼圖片不是複製那個網址嗎 01/18 16:48