[理工] [資結]-sort

看板Grad-ProbAsk作者 (小澤)時間16年前 (2009/12/17 11:01), 編輯推噓4(4推 0噓 18→)
留言22則, 7人參與, 最新討論串3/3 (看更多)
請問一下，當資料量很大的時候 排序速率: Quicksort > Mergesort > Heapsort 是為什麼? 是由程式run出來的結果，還是有定理或什麼可以證明 題目問why，不知道怎麼解釋 -- ┌這篇文章讓您覺得？─────────────────────────────┐ │ │ │ 一"一 \ / >\\\< ╯ ╰ ∩ ∩ ▁ ▁ ＞＿＜ ㄧ ㄧ+ │ │ 皿 ε □ ▽ ▇Δ ▇ ╰╯ ╯ │ │ 北七 亂喔 害羞 莎笅 爽啦 哭爸 ＸＤ 科科 │ └──────────────────────────────────────┘ -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 122.116.14.2
推
12/17 12:32, , 1F
定理的話 已經有人證明這三種sort在averge case情況下
12/17 12:32, 1F
→
12/17 12:33, , 2F
的複雜度 包含係數都可以算出來
12/17 12:33, 2F
→
12/17 18:16, , 3F
所以除非知道定理，不然考試沒辦法證明出來是吧~?
12/17 18:16, 3F
→
12/17 19:24, , 4F
跟計組第7章有關係
12/17 19:24, 4F
推
12/17 20:02, , 5F
我覺得他只是要你申論吧 看這三種演算法到底是快在哪..
12/17 20:02, 5F
→
12/17 20:02, , 6F
像Heapsort就說他還要維持一個heap的形狀 實做比較複雜 慢
12/17 20:02, 6F
→
12/17 20:03, , 7F
Mergesort要一個額外陣列搬來搬去 所以比不上quicksort
12/17 20:03, 7F
→
12/17 21:18, , 8F
怎麼怪怪的... Quicksort 應該是三者裡面最慢的
12/17 21:18, 8F
推
12/17 22:34, , 9F
樓上 Qiucksort在Average case下的確是最快的
12/17 22:34, 9F
→
12/17 22:36, , 10F
打錯 是Quicksort才對= =
12/17 22:36, 10F
→
12/17 23:07, , 11F
但它的 worst case 並非 O(nlogn)
12/17 23:07, 11F
→
12/17 23:12, , 12F
對程式的穩定性來說， Mergesort 和 Heapsort 再怎麼糟
12/17 23:12, 12F
→
12/17 23:13, , 13F
也只會到 O(nlogn) .Quicksort 快在有可能比 O(nlogn)
12/17 23:13, 13F
→
12/17 23:14, , 14F
還小，但只對特定情況才會如此
12/17 23:14, 14F
推
12/17 23:16, , 15F
是指"Average case"的情況下 Quicksort才最快
12/17 23:16, 15F
→
12/17 23:21, , 16F
恩，我知道， 只是我覺得實用性應該要倒過來 OTZ
12/17 23:21, 16F
→
12/18 00:33, , 17F
其實聖經本上面有平均時間的數據 Quick sort穩穩領先
12/18 00:33, 17F
→
12/18 06:57, , 18F
Average case下快為什麼實用性要倒過來
12/18 06:57, 18F
→
12/18 06:58, , 19F
程式的穩定性也不是用worst case當唯一指標吧
12/18 06:58, 19F
→
12/18 07:00, , 20F
Quicksort並不是快在有可能比O(nlogn)小，而是在大部分case
12/18 07:00, 20F
→
12/18 07:04, , 21F
比另外兩者快常數/低order的時間
12/18 07:04, 21F
→
12/18 07:05, , 22F
注意是大部分，反而應該說在特定情況才會比較慢
12/18 07:05, 22F
‣ 更多 polomoss 的文章
文章代碼(AID): #1BAPy9Yl (Grad-ProbAsk)
‣ 更多 polomoss 的文章
文章代碼(AID): #1BAPy9Yl (Grad-ProbAsk)