PTT職涯區 / Examination (國家考試)

[考題] 排序演算法

看板Examination (國家考試)作者時間13年前 (2013/01/30 22:57), 編輯推噓2(2推 0噓 0→)
留言2則, 1人參與, 最新討論串1/1
作者: 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)
推
01/31 09:30, , 1F
看了題目 感覺是翻譯錯誤 應該是best case
01/31 09:30, 1F
推
01/31 09:33, , 2F
也不能說題目錯 所有的sorting algo 必符合Omega(nlgn)
01/31 09:33, 2F
‣ 更多 panda555 的文章
文章代碼(AID): #1H2JJXS_ (Examination)
Examination 近期熱門文章
更多 近期熱門文章 >>
PTT職涯區 即時熱門文章
更多 即時熱門文章 >>
‣ 更多 panda555 的文章
文章代碼(AID): #1H2JJXS_ (Examination)