作者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