[轉錄][教學] 計概 排序複雜度 表格

[boyulin (Active study)]

※ [本文轉錄自 Army-Sir 看板]

作者: Liroy (Liroy) 看板: Army-Sir
標題: [教學] 計概 排序複雜度 表格
時間: Tue Jan 29 00:10:05 2008


常見的資料排序方法我列了一張表格

            ┌──────────────┐
            │         時間複雜度         │
┌─────┼────┬────┬────┼───┬──────────┐
│          │  最差  │  最佳  │  平均  │ 是否 │   空間複雜度       │
│          │ 複雜度 │ 複雜度 │ 複雜度 │ 穩定 │                    │
├─────┼────┼────┼────┼───┼──────────┤
│ Insert   │        │        │        │      │                    │
│  sort    │ O(n^2) │  O(n)  │ O(n^2) │  Yes │       O(1)         │
├─────┼────┼────┼────┼───┼──────────┤
│selection │        │        │        │      │                    │
│  sort    │ O(n^2) │ O(n^2) │ O(n^2) │  No  │       O(1)         │
├─────┼────┼────┼────┼───┼──────────┤
│  Bubble  │        │        │        │      │                    │
│   sort   │ O(n^2) │  O(n)  │ O(n^2) │  Yes │       O(1)         │
├─────┼────┼────┼────┼───┼──────────┤
│  Shell   │        │        │        │      │                    │
│  sort    │ O(n^2) │O(n^1.5)│ O(n^2) │  No  │       O(1)         │
├─────┼────┼────┼────┼───┼──────────┤
│  Quick   │        │        │        │      │                    │
│  sort    │ O(n^2) │O(nlogn)│O(nlogn)│  No  │   O(logn) or O(n)  │
├─────┼────┼────┼────┼───┼──────────┤
│  Merge   │        │        │        │      │                    │
│  sort    │O(nlogn)│O(nlogn)│O(nlogn)│  Yes │       O(n)         │
├─────┼────┼────┼────┼───┼──────────┤
│  Heap    │        │        │        │      │                    │
│  sort    │O(nlogn)│O(nlogn)│O(nlogn)│  No  │       O(1)         │
├─────┼────┼────┼────┼───┼──────────┤
│  Radix   │        │        │        │      │                    │
│   sort   │  O(n)  │  O(n)  │  O(n)  │  Yes │       O(r x n)     │
├─────┼────┼────┼────┼───┼──────────┤
│ Counting │        │        │        │      │                    │
│   sort   │  O(n)  │  O(n)  │  O(n)  │  Yes │    O(n) + O(k)     │
└─────┴────┴────┴────┴───┴──────────┘

以上log都是以2為底，不過底數並不會影響複雜度大小。

這是結果論。每個複雜度的証明，我...有點懶...XXXD

大家就把表格熟記，就天下無敵了！！！！

--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 59.105.172.111
推 damson:感謝!
推 abcdkoala:有看有推~
推 pili012140:謝謝~這很有用喔
推 amliguous:佛心來著的阿
推 king510:推一下...很熱心
→ f910567:敬禮!( ￣□￣)/  <(￣ㄧ￣ ) <(￣ㄧ￣ ) <(￣ㄧ￣ )
推 SuperMike:好強Orz
→ Liroy:Shell，Radix和Counting應該都不會考。所以這三個可以忽略
推 mybestname:真的有幫助! 謝謝L大^^
→ Liroy:最後，我要去睡了～囧...有問題，明天再幫忙解吧:)
推 hun1112:大推~~
推 safari79:千華95年的版本描述quick、heap、merge的平均比較次數
推 carlyu:大推
→ safari79:是nlog2n(2要下標)，是不是錯了呀
→ Liroy:比較次數的話，就要講解他的排序方式了...
→ Liroy:哪個nlog2n?!
→ safari79:他是寫排序之複雜度(平均比較次數)
→ Liroy:喔喔～看懂了。在複雜度裡面，底數是不會影響的喔～不過的確
→ Liroy:以上所有log都是2為底。XXXXXD
推 Ryx:沒差吧 用2或用10都一樣不是嗎
→ Ryx:喔喔 我推太慢了 = ="
推 safari79:所以有沒有2 都是一樣的表示方法 沒錯摟?!
→ Ryx:複雜度用誰為底都沒有影響  但是這裡面的都是以2為底
→ Liroy:O(以2為底的nlogn) = O(以10為底的nlogn)，不過考卷都會寫2
→ safari79:謝謝liroy的詳解 ~
※ 編輯: Liroy           來自: 59.105.172.111       (01/29 00:38)
→ Liroy:我補充了一句，有關底數的迷思了^^a...
推 mirepa:感嗯啊...
推 trojan203:你太神啦!!推
推 nonname1028:有看有推~~~
推 AppliedBigLP:大感謝!!!!!!! Thanks!
推 vivantan:請問SHELL的平均複雜度有沒有錯阿？不是nlogn 嗎？
→ Liroy:Shell應該沒有辦法達到nlogn喔...@@a
推 bheegrl:有看有推
→ Liroy:http://mis.im.tku.edu.tw/~tweety15c/index.htm
→ Liroy:資料結構動態教學網站
推 stoneaesther:感恩!!!
推 foxis:推一下 找好久了
推 peter316:Li大 這連結 有看有推  不錯用!!  @@b
推 Johnnystar:有看有推~~感謝
推 leo0910:感謝阿~~
→ neverend06:希望對您有幫助 http://Now.to/1l1
--
※ 發信站: 批踢踢實業坊(ptt.cc) 
◆ From: 220.139.234.177