普考-資訊處理計算機概要108 年第 24 題單選題

若有 $n$ 個數字欲進行排序，關於排序演算法的敘述，下列何者正確？

A合併排序法（merge sort）最差狀況的時間複雜度是

θ (n^{2})

B插入排序法（insertion sort）平均狀況的時間複雜度是

θ (n lo g n)

C快速排序法（quick sort）最差狀況的時間複雜度是

θ (n^{2})

正確答案

D堆積排序法（heap sort）最差狀況的時間複雜度是

θ (n^{2})

答案與詳解

正確答案

Quick sort 最差狀況(已排序且 pivot 選極值)時間複雜度為

θ (n^{2})

,故選 (C)。

A合併排序法（merge sort）最差狀況的時間複雜度是 $\theta(n^{2})$✕ 錯誤

錯誤。Merge sort 最差為 $\theta(n\log n)$,因為每次都對半分割。

B插入排序法（insertion sort）平均狀況的時間複雜度是 $\theta (\mathrm{n}\log \mathrm{n})$✕ 錯誤

錯誤。Insertion sort 平均為 $\theta(n^2)$,需平均比較約 $n^2/4$ 次。

C快速排序法（quick sort）最差狀況的時間複雜度是 $\theta(n^{2})$✓ 正確

D堆積排序法（heap sort）最差狀況的時間複雜度是 $\theta(n^{2})$✕ 錯誤

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

精選詳解

若有 n 個數字欲進行排序，關於排序演算法的敘述，下列何者正確？