作者smtp25 (irrationality)
看板Army-Sir
標題Re: [問題] 關於計概排序法最好情況最壞情況的算法
時間Thu Sep 12 14:48:16 2013
※ 引述《tonyycool (正)》之銘言：
: 2.下列有關排序演算法複雜度的敘述，何者為非
: (A)Bubble sort最壞狀況為O(n^2)，最佳為O(n)
: (B)Two-way Merge Sort 最壞狀況為O(nlog2 n)，最佳為O(n)
: (C)Binary tree Sort 最壞狀況為O(nlog2 n)，最佳為O(nlog2 n)
: (D)Heap Sort最壞的狀況為O(nlog2 n)，最佳為O(nlog2 n)
: ANS:C
這題答案是C還是B??
怎有兩種版本??
http://meo22.wwlc.nthu.edu.tw/military/attach/test/ <==答案是B
我自己查 Merge Sort不是都 O(nlog2 n)嗎??
Binary tree Sort 是最壞O(nlog2 n) 最佳為 O(n)
兩個都不對阿 @__@
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 36.233.200.172
※ 編輯: smtp25 來自: 36.233.200.172 (09/12 14:57)
1F：→ jdtrue:BC都錯 Merge Sort好壞平均都是O(nlog2 n) 09/13 00:07
2F：→ jdtrue:Binary Tree Sort即等同建立二元搜尋樹的time complexity 09/13 00:08
3F：→ jdtrue:最好是一次放到底O(n) 最差是每次都比到最後一層O(nlog2 n) 09/13 00:09
4F：→ jdtrue:阿不對 最差是O(n^2)才對 就插入新元素到已排序的資料裡 09/13 00:20
5F：→ jdtrue:O(nlog2 n)是average case 09/13 00:21