國中教甄｜資訊科技資訊科技109 年第 27 題單選題
以下是某一種排序演算法的片段：procedure sort(a, left, right)if right > leftselect a pivot value a[pivotIndex]pivotNewIndex := partition(a, left, right, pivotIndex)sort(a, left, pivotNewIndex-1)sort(a, pivotNewIndex+1, right)根據上述排序演算法的的描述，下列何者正確？
A這種排序演算法的平均時間複雜度為O(logn)
B這種排序演算法的最差時間複雜度為O(n²)正確答案
C這種排序演算法的最佳時間複雜度為O(logn)
D這種排序演算法的平均空間複雜度為O(n²)
B正確答案
題目描述的虛擬碼為快速排序法，其最差時間複雜度為 O(n²)。
逐選項解析
A這種排序演算法的平均時間複雜度為O(logn)✕ 錯誤
快速排序法的平均時間複雜度為 O(n log n)，而非 O(log n)。
B這種排序演算法的最差時間複雜度為O(n²)✓ 正確
快速排序法在最差情況（例如陣列已排序且基準值選取不佳）下，每次分割僅減少一個元素，導致時間複雜度退化為 O(n²)。
C這種排序演算法的最佳時間複雜度為O(logn)✕ 錯誤
D這種排序演算法的平均空間複雜度為O(n²)✕ 錯誤
立即註冊,看完整詳解
這題的完整詳解,註冊就能看 · 每天 2 題免費
- 完整逐選項解析
- 秒殺解題技巧與破題關鍵
- 關鍵知識表整理
- 陷阱與易錯提醒
- 同考點歷屆題庫連續刷題與錯題本
