設 為欲排序的數值的個數，下列關於排序演算法的敘述，何者正確？
A快速排序法（quick sort）在最差狀況（worst-case）的時間複雜度為
B合併排序法（merge sort）在最差狀況（worst-case）的時間複雜度為 正確答案
C就最差時間複雜度而言，快速排序法優於合併排序法
D就最差時間複雜度而言，氣泡排序法（bubble sort）優於快速排序法
答案與詳解
逐選項解析
A快速排序法（quick sort）在最差狀況（worst-case）的時間複雜度為 $O(n \log n)$✕ 錯誤
錯誤。快速排序的最差時間複雜度為 $O(n^2)$,發生於 pivot 選擇不當(如已排序資料),平均才是 $O(n \log n)$。
B合併排序法（merge sort）在最差狀況（worst-case）的時間複雜度為 $O(n \log n)$✓ 正確
正確。合併排序採分治法,遞迴樹高度 $\log n$,每層合併成本 $O(n)$,因此最差、平均、最佳皆為 $O(n \log n)$。
C就最差時間複雜度而言，快速排序法優於合併排序法✕ 錯誤
D就最差時間複雜度而言，氣泡排序法（bubble sort）優於快速排序法✕ 錯誤
立即註冊,看完整詳解
這題的完整詳解,註冊就能看 · 每天 2 題免費
- 完整逐選項解析
- 秒殺解題技巧與破題關鍵
- 關鍵知識表整理
- 陷阱與易錯提醒
- 同考點歷屆題庫連續刷題與錯題本
立即註冊觀看完整詳解 已有帳號?登入
