Q126.
假設n 代表資料數量，有關Quick Sort 排序演算法在Best Case 之計算時間，下列何者是正確？
電腦軟體設計共同科目 · 乙級 · Q126
難易度分析
2 / 5
本題屬於基礎概念的記憶型題目，僅需正確區分排序演算法在不同情境下的時間複雜度即可得出結論。
正確答案：①θ(n log n)
① θ(n log n):快速排序法在最佳情況下，每次樞紐元素(pivot)都能將陣列均勻分割為兩個大小相近的子陣列，遞迴深度為 log n，每層分割需進行 O(n) 次比較，因此總時間複雜度為 θ(n log n)。
錯誤選項解析
- ② θ(n 2):θ(n²) 是快速排序法的最壞情況時間複雜度，發生於輸入資料已排序或逆序且樞紐選取策略不佳時，導致每次分割極度不平衡，遞迴深度退化為 n 層。
- ③ θ(n):θ(n) 並非快速排序法的任何情況時間複雜度，此複雜度通常出現在線性掃描演算法（如遍歷陣列尋找最大值），排序演算法基於比較的下界為 Ω(n log n)。
- ④ θ(1):θ(1) 代表常數時間，僅適用於不需處理資料的操作（如存取陣列索引），排序演算法必須比較並移動元素，不可能達到常數時間。
Learning Tip
"快速排序法的效能高度依賴樞紐選取策略，考試常混淆最佳情況 θ(n log n)、平均情況 θ(n log n) 與最壞情況 θ(n²)。實務上可採用隨機化樞紐或三數取中法來避免最壞情況發生，並注意 θ 表示緊確界，與 O（上界）符號意義不同。"
學員答題分佈
①θ(n log n)0%
②θ(n 2)0%
③θ(n)0%
④θ(1)0%
此答題分佈是根據學員在 LongePass 模擬考等實際作答紀錄計算而成。與考友分享這道歷屆試題與詳細解析！