關務人員考試關務四等-資訊處理(選試英文)科別計算機概要114 年第 22 題單選題

若使用插入排序法（Insertion Sort）對 $n$ 個數字由小到大進行排序，則在最差的情況下（Worst Case），時間複雜度為何？

O (1)

O (n)

O (n lo g n)

O (n^{2})

正確答案

答案與詳解

正確答案

插入排序最差情況(完全逆序)需比較與移動約 n(n-1)/2 次,時間複雜度為

O (n^{2})

。

正確。最差情況(逆序)需 n(n-1)/2 次比較與搬移,為 $O (n^{2})$ 。

載入中…

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

若使用插入排序法（Insertion Sort）對 n 個數字由小到大進行排序，則在最差的情況下（Worst Case），時間複雜度為何？