設 $n$ 為欲排序的數值的個數，下列關於排序演算法的敘述，何者正確？

A快速排序法（quick sort）在最差狀況（worst-case）的時間複雜度為

O (n lo g n)

B合併排序法（merge sort）在最差狀況（worst-case）的時間複雜度為

O (n lo g n)

正確答案

C就最差時間複雜度而言，快速排序法優於合併排序法

D就最差時間複雜度而言，氣泡排序法（bubble sort）優於快速排序法

答案與詳解

正確答案

合併排序法在最差情況下時間複雜度為 O(n log n),選 B。

正確。合併排序採分治法,遞迴樹高度 $lo g n$ ,每層合併成本 $O (n)$ ,因此最差、平均、最佳皆為 $O (n lo g n)$ 。

載入中…

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

設 n 為欲排序的數值的個數，下列關於排序演算法的敘述，何者正確？