Q214.
假設輸入資料有n 個，在最糟情形下，下列那些排序法的時間複雜度不是θ(nlogn)？此處n 為資料個數
電腦軟體設計共同科目 · 乙級 · Q214
難易度分析
3 / 5
本題屬於複選題，要求考生精確區分多種排序演算法在最糟情況下的時間複雜度。由於必須對所有選項的複雜度模型進行獨立判定且無一遺漏才能得分，增加了認知負荷與判別難度。
正確答案 (複選)：①, ②, ③, ④
- ① Insertion Sort:Insertion Sort（插入排序法）在最糟情況（陣列完全反向）下，需進行 n(n-1)/2 次比較與移動，時間複雜度為 O(n²)，而非 θ(nlogn)。
- ② Shell Sort:Shell Sort（希爾排序法）的時間複雜度取決於間隔序列（gap sequence）的選擇，使用原始 Shell 間隔時最糟情況為 O(n²)，即使採用較佳的 Hibbard 或 Sedgewick 序列也無法達到 θ(nlogn)。
- ③ Selection Sort:Selection Sort（選擇排序法）無論最好或最糟情況，均需執行 n(n-1)/2 次比較以尋找最小元素，時間複雜度固定為 O(n²)，不屬於 θ(nlogn)。
- ④ Radix Sort:Radix Sort（基數排序法）為非比較型排序法，時間複雜度為 O(d×(n+k))，其中 d 為位數、k 為基底範圍，其複雜度模型與 θ(nlogn) 的比較型排序下限完全不同。
錯誤選項解析
Learning Tip
"本題核心考點在於區分比較型排序與非比較型排序的時間複雜度模型。需特別注意：θ(nlogn) 僅為比較型排序的理論下限（如 Merge Sort、Heap Sort 可達此界），而 Insertion Sort、Selection Sort 等基礎演算法最糟情況均為 O(n²)。Radix Sort 屬於線性時間排序，不受比較排序下限限制，但其複雜度表達式也非 θ(nlogn)。常見陷阱是誤認 Shell Sort 為高效排序即等同 θ(nlogn)，實際上其複雜度仍依賴間隔序列設計。"
學員答題分佈
①Insertion Sort0%
②Shell Sort0%
③Selection Sort0%
④Radix Sort0%
此答題分佈是根據學員在 LongePass 模擬考等實際作答紀錄計算而成。與考友分享這道歷屆試題與詳細解析！
