普考-資訊處理計算機概要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)。

正確。當資料已排序或反向排序且選最左/最右為 pivot 時,每次分割只少 1 個元素,遞迴式 $T (n) = T (n - 1) + O (n) \Rightarrow θ (n^{2})$ 。

載入中…

Examly 收錄 38 萬+ 道歷屆題目，每題都有像這樣的精選詳解。免費下載，立即開練。

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