原住民族考試四等考試-電子工程類科計算機概要106 年第 23 題單選題

使用選擇排序法（selection sort）對 $n$ 個數字排序，在最佳情況（best case）及最糟情況（worst case）下，其時間複雜度（time complexity）為何？

A最佳情況：

Θ (n)

；最糟情況：

Θ (n^{2})

B最佳情況：

Θ (n^{2})

；最糟情況：

Θ (n^{2})

正確答案

C最佳情況：

Θ (n)

；最糟情況：

Θ (n lo g n)

D最佳情況：

Θ (n lo g n)

；最糟情況：

Θ (n^{2})

答案與詳解

正確答案

選擇排序不論輸入為何,皆需完整比較,最佳與最糟皆為

Θ (n^{2})

。

正確。選擇排序的比較次數固定為 $\frac{n ( n - 1 )}{2}$ ,最佳與最糟都是 $Θ (n^{2})$ 。

載入中…

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

使用選擇排序法（selection sort）對 n 個數字排序，在最佳情況（best case）及最糟情況（worst case）下，其時間複雜度（time complexity）為何？