推 carterdunk:看了題目 感覺是翻譯錯誤 應該是best case 01/31 09:30
推 carterdunk:也不能說題目錯 所有的sorting algo 必符合Omega(nlgn) 01/31 09:33
作者: 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)