Q213.
假設輸入資料有n 個，在最糟情形下，下列那些排序法的時間複雜度為θ(nlogn)？此處n 為資料個數 。
電腦軟體設計共同科目 · 乙級 · Q213
難易度分析
3 / 5
本題要求區分多種排序演算法在特定極端情況下的效能表現。由於涉及複選判斷，且需精準區分平均情況與最糟情況的差異，增加了分析難度。
正確答案 (複選)：③, ④
- ③ Heap Sort:堆積排序 (Heap Sort) 利用 二元堆積 (Binary Heap) 結構進行排序，無論資料初始狀態為何，建立堆積與反覆取出根節點的操作皆維持 θ(nlogn) 的最糟時間複雜度，具備穩定的效能保證。
- ④ Merge Sort:合併排序 (Merge Sort) 採用 分治法 (Divide and Conquer) 策略，將資料遞迴對半分割後再合併，其遞迴樹深度恆為 log n，每層合併操作為 O(n)，故最糟時間複雜度恆為 θ(nlogn)。
錯誤選項解析
- ① Bubble Sort:氣泡排序 (Bubble Sort) 的最糟時間複雜度為 O(n²)，因為其透過相鄰元素兩兩比較並交換，即使資料已部分排序仍需進行多輪遍歷，不具備 θ(nlogn) 的效能。
- ② Quick Sort:快速排序 (Quick Sort) 的平均時間複雜度為 O(nlogn)，但在最糟情況（如：已排序資料且樞紐選取不當）時會退化為 O(n²)，因此不符合題目要求的最糟 θ(nlogn) 條件。
Learning Tip
"此類題型常考陷阱在於混淆平均情況與最糟情況的時間複雜度。快速排序雖平均效能優異，但最糟為 O(n²)；而 Heap Sort 與 Merge Sort 兩者皆能保證最糟 θ(nlogn)，差異在於 Heap Sort 為原地排序 (in-place) 且不穩定，Merge Sort 需額外空間但為穩定排序。實務上應根據記憶體限制與穩定性需求選擇合適演算法。"
學員答題分佈
①Bubble Sort0%
②Quick Sort0%
③Heap Sort0%
④Merge Sort0%
此答題分佈是根據學員在 LongePass 模擬考等實際作答紀錄計算而成。與考友分享這道歷屆試題與詳細解析！