Q31.
假設n 代表資料數量，針對排序演算法，下列之描述何者正確？
電腦軟體設計共同科目 · 乙級 · Q31
難易度分析
3 / 5
本題要求考生對多種排序演算法在最壞情況下的時間複雜度有精確的記憶與區分能力，且需能正確辨識非標準的數學符號表示法。
正確答案：③Insertion Sort 在最壞情況下所需之計算複雜度為θ(n 2)
③ Insertion Sort 在最壞情況下所需之計算複雜度為θ(n 2):Insertion Sort 在最壞情況下（資料完全反向）需進行 n(n-1)/2 次比較與交換，因此時間複雜度為 θ(n²)，此描述正確。
錯誤選項解析
- ① Quick Sort 在最壞情況下所需之時間複雜度為θ(n log n):Quick Sort 在最壞情況下（已排序或反向排序資料且樞紐選擇不當）的時間複雜度為 θ(n²)，而非 θ(n log n)。θ(n log n) 是其平均情況的複雜度。
- ② Radix Sort在最壞情況下所需之時間複雜度為θ(n log n):Radix Sort 的時間複雜度為 θ(d·(n + k))，其中 d 為位數、k 為基數範圍，屬於非比較型排序，其複雜度與 θ(n log n) 無關。
- ④ Heap Sort 在最壞情況下所需之時間複雜度為θ(n 2):Heap Sort 無論最佳、平均或最壞情況，時間複雜度皆為 θ(n log n)，因為建立堆積與調整堆積的成本固定為對數級別，而非 θ(n²)。
Learning Tip
"此類題型常考各排序演算法的時間複雜度比較。需特別注意：Quick Sort 最壞情況為 θ(n²)，而 Heap Sort 穩定維持 θ(n log n) 是其優勢。Insertion Sort 僅在資料量小或近似排序時效率較佳。另外，θ(n²) 在題目中可能寫成 θ(n 2) 的形式，需能正確辨識。"
學員答題分佈
①Quick Sort 在最壞情況下所需之時間複雜度為θ(n log n)0%
②Radix Sort在最壞情況下所需之時間複雜度為θ(n log n)0%
③Insertion Sort 在最壞情況下所需之計算複雜度為θ(n 2)0%
④Heap Sort 在最壞情況下所需之時間複雜度為θ(n 2)0%
此答題分佈是根據學員在 LongePass 模擬考等實際作答紀錄計算而成。與考友分享這道歷屆試題與詳細解析！