→ beargg0305: 註明一下 第一張圖是101交大 01/21 17:29
推 yupog2003: 我反而覺得有問題的是交大，因為用merge sort排序6個 01/21 17:34
→ yupog2003: 數字我算worst case只要9次comparisons 01/21 17:34
推 yupog2003: 但是照log(n!)取上限來看，的確又是10次沒錯@@ 01/21 17:42
推 newpuma: 第一題我也是算lg(6!)上限 01/21 17:42
→ yupog2003: 不過你看一下我列6個數字的： 01/21 17:46
→ yupog2003: [a1,a2],[a3,a4],[a5,a6] => 3次 01/21 17:46
→ yupog2003: [[a1,a2],[a3,a4]],[a5,a6] =>把左邊兩個merge只要2次 01/21 17:48
→ yupog2003: [a1,a2,a3,a4,a5,a6] =>4個元素和2個元素merge最多只要 01/21 17:49
→ yupog2003: 4次，3+2+4=9，我已經盡量舉worst case了 01/21 17:49
→ yupog2003: 再來列4個數字的： 01/21 17:50
→ yupog2003: [a1,a2],[a3,a4] => 2次 01/21 17:50
→ yupog2003: [a1,a2,a3,a4] => merge皆為2個元素的list只要2次 01/21 17:51
→ yupog2003: 2+2=4，確實worst case只要四次 01/21 17:52
→ beargg0305: 第二階段左邊的RUN應該可以到3次 01/21 17:52
→ yupog2003: 當然也可以不要這樣merge，就可以超過我上面說的那些數 01/21 17:52
→ yupog2003: 字，不過這樣我對worst case的定義就有點模糊了... 01/21 17:53
→ yupog2003: oh~對耶，你解答我的疑惑了，那清大這個怪怪的+1，交大 01/21 17:54
→ yupog2003: 沒問題XD感謝b大解了我放在心中已久的疑問 01/21 17:54
→ beargg0305: 其實我也不太懂這裡的worst case是指啥 01/21 17:54
→ beargg0305: 假如說排序3個數 01/21 17:54
→ beargg0305: 有時候可以2次有時候3次 01/21 17:54
→ yupog2003: 那清大那個的確worst case是at least 5次比較合理@@ 01/21 17:55
→ yupog2003: 之前一直把兩兩merge想成2次，其實應該最多3次... 01/21 17:56
→ ken52011219: 假設 一數列從大到小or 從小到大 sort 01/21 18:16
→ ken52011219: 若本來就依大小排列 至少4次即可比較完 @@? 01/21 18:17
→ ken52011219: 不對 我想錯了QQ 01/21 18:22
→ ken52011219: 是用非比較式 演算法即可達成吧 01/21 18:23
→ ken52011219: 並非與相異值比較，而是與對應的bucket index比較 01/21 18:24
→ ken52011219: 查了一下 好像公式是 3/2N - 2 when n 為even@@ 01/21 18:38
→ ken52011219: 想了一下，令一state 為 {min , max}隨意抓取兩數 01/21 18:50
→ ken52011219: 比較大小決定 {min ,max}值 01/21 18:50
→ ken52011219: 再抓取未選的其中之一數 與{min,max}比較並更新 01/21 18:51
→ ken52011219: {min,max}的值 共三次比較 01/21 18:52
→ ken52011219: 最後將非min,max值 拿來比較 共四次 01/21 18:53
→ ken52011219: 我覺得這個方法是延伸至 尋找最大最小值的變化 01/21 18:53
推 PTTleader: 第三個數 跟min max 比較 worstcase 要兩次吧 01/21 18:56
→ ken52011219: 對耶@_@ 01/21 19:37
推 YuxiWen: [取上界(lg(6!))]- 1 不是等於9嗎？ 01/21 20:26
→ yupog2003: 為什麼要-1呢？ 01/21 20:56
→ YuxiWen: 因為dicision tree結果在葉子上，但比較在祖先結點，所以 01/21 22:22
→ YuxiWen: 比較次數其實是直系祖先數即葉子在的高度-1 01/21 22:22
→ YuxiWen: 我是這樣想的 01/21 22:22
→ yupog2003: 其實是不用-1的，舉個例子，兩個數排序只要1次比較 01/21 23:11
→ yupog2003: log(2!)=1，如果-1的話就變成只要0次比較了 01/21 23:12
→ yupog2003: 3個數排序需要3次比較，log(3!)取上限=3，如果-1的話就 01/21 23:13
→ yupog2003: 變成2次比較，顯然不合理，畫個圖比較明顯 01/21 23:14
推 yorunohoshi: 這題應該是題目出錯可能性比較大 如果input size 4 01/21 23:32
→ yorunohoshi: 可以用4次比較就搞定 那comparison-based model下的 01/21 23:32
→ yorunohoshi: sorting lower bound 就會是omega(n)而不是nlogn 01/21 23:33