[理工] sorting的比較次數

看板Grad-ProbAsk作者 (bear)時間9年前 (2017/01/21 17:22), 9年前編輯推噓6(6推 0噓 44→)
留言50則, 7人參與, 最新討論串1/1
如果是基於比較原理的排序 那麼在worst case下的比較次數至少為多少？ 個人認為是由root到樹葉的路徑長 也就是樹高-1 所以應當是 >= lg(leaf數)取上限 http://i.imgur.com/l4JpV8e.jpg
如果照交大這題答案會是10沒錯 http://i.imgur.com/dK0GvQg.jpg
但是清大這題怎麼說是4次 不是應該5次嗎？ -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 114.136.42.9 ※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1484990527.A.3D7.html ※ 編輯: beargg0305 (114.136.42.9), 01/21/2017 17:23:01
→
01/21 17:29, , 1F
註明一下 第一張圖是101交大
01/21 17:29, 1F
推
01/21 17:34, , 2F
我反而覺得有問題的是交大，因為用merge sort排序6個
01/21 17:34, 2F
→
01/21 17:34, , 3F
數字我算worst case只要9次comparisons
01/21 17:34, 3F
推
01/21 17:42, , 4F
但是照log(n!)取上限來看，的確又是10次沒錯@@
01/21 17:42, 4F
推
01/21 17:42, , 5F
第一題我也是算lg(6!)上限
01/21 17:42, 5F
→
01/21 17:46, , 6F
不過你看一下我列6個數字的：
01/21 17:46, 6F
→
01/21 17:46, , 7F
[a1,a2],[a3,a4],[a5,a6] => 3次
01/21 17:46, 7F
→
01/21 17:48, , 8F
[[a1,a2],[a3,a4]],[a5,a6] =>把左邊兩個merge只要2次
01/21 17:48, 8F
→
01/21 17:49, , 9F
[a1,a2,a3,a4,a5,a6] =>4個元素和2個元素merge最多只要
01/21 17:49, 9F
→
01/21 17:49, , 10F
4次，3+2+4=9，我已經盡量舉worst case了
01/21 17:49, 10F
→
01/21 17:50, , 11F
再來列4個數字的：
01/21 17:50, 11F
→
01/21 17:50, , 12F
[a1,a2],[a3,a4] => 2次
01/21 17:50, 12F
→
01/21 17:51, , 13F
[a1,a2,a3,a4] => merge皆為2個元素的list只要2次
01/21 17:51, 13F
→
01/21 17:52, , 14F
2+2=4，確實worst case只要四次
01/21 17:52, 14F
→
01/21 17:52, , 15F
第二階段左邊的RUN應該可以到3次
01/21 17:52, 15F
→
01/21 17:52, , 16F
當然也可以不要這樣merge，就可以超過我上面說的那些數
01/21 17:52, 16F
→
01/21 17:53, , 17F
字，不過這樣我對worst case的定義就有點模糊了...
01/21 17:53, 17F
→
01/21 17:54, , 18F
oh~對耶，你解答我的疑惑了，那清大這個怪怪的+1，交大
01/21 17:54, 18F
→
01/21 17:54, , 19F
沒問題XD感謝b大解了我放在心中已久的疑問
01/21 17:54, 19F
→
01/21 17:54, , 20F
其實我也不太懂這裡的worst case是指啥
01/21 17:54, 20F
→
01/21 17:54, , 21F
假如說排序3個數
01/21 17:54, 21F
→
01/21 17:54, , 22F
有時候可以2次有時候3次
01/21 17:54, 22F
→
01/21 17:55, , 23F
那清大那個的確worst case是at least 5次比較合理@@
01/21 17:55, 23F
→
01/21 17:56, , 24F
之前一直把兩兩merge想成2次，其實應該最多3次...
01/21 17:56, 24F
→
01/21 18:16, , 25F
假設 一數列從大到小or 從小到大 sort
01/21 18:16, 25F
→
01/21 18:17, , 26F
若本來就依大小排列 至少4次即可比較完 @@?
01/21 18:17, 26F
→
01/21 18:22, , 27F
不對 我想錯了QQ
01/21 18:22, 27F
→
01/21 18:23, , 28F
是用非比較式 演算法即可達成吧
01/21 18:23, 28F
→
01/21 18:24, , 29F
並非與相異值比較，而是與對應的bucket index比較
01/21 18:24, 29F
→
01/21 18:38, , 30F
查了一下 好像公式是 3/2N - 2 when n 為even@@
01/21 18:38, 30F
→
01/21 18:50, , 31F
想了一下，令一state 為 {min , max}隨意抓取兩數
01/21 18:50, 31F
→
01/21 18:50, , 32F
比較大小決定 {min ,max}值
01/21 18:50, 32F
→
01/21 18:51, , 33F
再抓取未選的其中之一數 與{min,max}比較並更新
01/21 18:51, 33F
→
01/21 18:52, , 34F
{min,max}的值 共三次比較
01/21 18:52, 34F
→
01/21 18:53, , 35F
最後將非min,max值 拿來比較 共四次
01/21 18:53, 35F
→
01/21 18:53, , 36F
我覺得這個方法是延伸至 尋找最大最小值的變化
01/21 18:53, 36F
推
01/21 18:56, , 37F
第三個數 跟min max 比較 worstcase 要兩次吧
01/21 18:56, 37F
→
01/21 19:37, , 38F
對耶@_@
01/21 19:37, 38F
推
01/21 20:26, , 39F
[取上界(lg(6!))]- 1 不是等於9嗎？
01/21 20:26, 39F
→
01/21 20:56, , 40F
為什麼要-1呢？
01/21 20:56, 40F
→
01/21 22:22, , 41F
因為dicision tree結果在葉子上，但比較在祖先結點，所以
01/21 22:22, 41F
→
01/21 22:22, , 42F
比較次數其實是直系祖先數即葉子在的高度-1
01/21 22:22, 42F
→
01/21 22:22, , 43F
我是這樣想的
01/21 22:22, 43F
→
01/21 23:11, , 44F
其實是不用-1的，舉個例子，兩個數排序只要1次比較
01/21 23:11, 44F
→
01/21 23:12, , 45F
log(2!)=1，如果-1的話就變成只要0次比較了
01/21 23:12, 45F
→
01/21 23:13, , 46F
3個數排序需要3次比較，log(3!)取上限=3，如果-1的話就
01/21 23:13, 46F
→
01/21 23:14, , 47F
變成2次比較，顯然不合理，畫個圖比較明顯
01/21 23:14, 47F
推
01/21 23:32, , 48F
這題應該是題目出錯可能性比較大 如果input size 4
01/21 23:32, 48F
→
01/21 23:32, , 49F
可以用4次比較就搞定 那comparison-based model下的
01/21 23:32, 49F
→
01/21 23:33, , 50F
sorting lower bound 就會是omega(n)而不是nlogn
01/21 23:33, 50F
‣ 更多 beargg0305 的文章
文章代碼(AID): #1OWoW_FN (Grad-ProbAsk)