Quick sort 是著名的排序演算法，下列何者是其平均的時間複雜度？ (A) $O(n)$ (B) $O(n \log n)$ (C) $O(n^{2})$ (D) $O(2n)$ 。

國小教甄｜資訊科技資訊科技106 年第 9 題單選題

Quick sort 是著名的排序演算法，下列何者是其平均的時間複雜度？

A$O(n)$

B$O(n \log n)$正確答案

C$O(n^{2})$

D$O(2n)$ 。

答案與詳解

正確答案

Quick sort（快速排序）在平均情況下的時間複雜度為 O(n log n)。

A$O(n)$✕ 錯誤

O(n) 為線性時間複雜度，Quick sort 無法在平均情況下達到此效率，此複雜度常見於計數排序（Counting sort）或基數排序（Radix sort）等非比較型排序演算法。

B$O(n \log n)$✓ 正確

Quick sort 採用分治法（Divide and Conquer），平均情況下每次分割能將資料大致平分，遞迴深度為 log n，每層需處理 n 個元素，故平均時間複雜度為 O(n log n)。

C$O(n^{2})$✕ 易錯陷阱

D$O(2n)$ 。✕ 錯誤

這題的完整詳解,註冊就能看 · 每天 2 題免費

精選詳解