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

在一個長度為 $n$ 的陣列中，若要同時找出「最大值」與「最小值」，最少需要比較多少次才能完成？（不考慮其他資料結構或額外輔助陣列）

n - 1

2 (n - 1)

\frac{2}{3} n

1.5 (n - 1)

正確答案

答案與詳解

正確答案

兩兩配對先比較,再分別找max/min,共需約 1.5(n-1) 次比較。

正確。配對比較法可達 3n/2-2 ≈ 1.5(n-1) 次,為最少比較次數。

載入中…

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

在一個長度為 n 的陣列中，若要同時找出「最大值」與「最小值」，最少需要比較多少次才能完成？（不考慮其他資料結構或額外輔助陣列）