國家安全情報人員考試五等考試-資訊組計算機大意110 年第 28 題單選題

如果使用快速排序法（quick sort ）進行排序 ${a_{1}, a_{2}, ..., a_{n}}$ 資料，則最壞（worst case）排序時間正比於多少？

lo g (n)

n

n \times lo g (n)

n \times n

正確答案

答案與詳解

正確答案

快速排序法在最壞情況下的時間複雜度為

O (n^{2})

,正比於

n \times n

。

正確。最壞情況下分割極不平衡,時間複雜度為 $O (n^{2})$ 。

載入中…

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

如果使用快速排序法（quick sort ）進行排序{a1​,a2​,...,an​} 資料，則最壞（worst case）排序時間正比於多少？