作者: panda555 (我是胖达不是胖呆哟^ ^) 看板: Examination
标题: [考题] 排序演算法
时间: Wed Jan 30 22:57:31 2013
100 年公务人员特种考试原住民族考试试题
等 别：四等考试
类 科：电子工程
科 目：计算机概要
7 以比较和交换为主的排序演算法的时间复杂度的下限（worst-case）是：
(a) nlogn
(b) n平方
(c) n平方logn
(d) logn
http://wwwc.moex.gov.tw/ExamQuesFiles/Question/100/100200_6416.pdf
ANS:(A)
可是Comparison BASED sorting 的Sort Average Cases上限为O(n log n)
代表下限一定超过nlogn阿
随便举一个quick sort的worst case也为O(n 平方)阿
是不试题目有错阿@@
感谢大大解惑
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 140.114.79.201
※ 编辑: panda555 来自: 140.114.79.201 (01/30 22:57)
※ 编辑: panda555 来自: 140.114.79.201 (01/30 22:58)
1F：推 carterdunk:看了题目 感觉是翻译错误 应该是best case 01/31 09:30
2F：推 carterdunk:也不能说题目错 所有的sorting algo 必符合Omega(nlgn) 01/31 09:33