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 的時間啊？
還是我的觀念有錯嗎？
謝謝大家幫解惑^^

第一題decision tree解 你上面不就有寫了

48(c) log V 應該沒錯24 題比較難一般的 sorting lower bound 是用 comparison 證明的但是 linear decision tree model 也可以證明https://algs4.cs.princeton.edu/65reductions/所以 24 (c) 要看你怎麼解釋linear decision tree 的 lower bound 會 implycomparison model 的 lower bound但是大部分課本上都是只證明 comparison model 的..24 (d) 的話 因為 non-linear 可能會提供 extra power所以有可能可以 beat O(n lg n)

回水餃大大是的，但是不知道這樣是不是對的因為那個應該是ave. case，但是題目是問worst case謝謝F大這麼詳盡的講解

說個題外話 你知道貼圖片不是複製那個網址嗎