地方政府公務人員四等-資訊處理類科計算機概要104 年第 30 題單選題

利用快速排序法（quick sort）於①當輸入資料已經排序好（sorted input）、②當輸入資料已經反向排序好（reverse-ordered input）及③當輸入資料是隨機（random input）時，快速排序法其執行時間分別為何？

O (N lo g N)

O (N lo g N)

O (N^{2})

正確答案

O (N lo g N)

O (N lo g N)

O (N)

正確答案

O (N lo g N)

O (N lo g N)

O (N lo g N)

正確答案

O (N lo g N)

O (N)

O (N^{2})

正確答案

答案與詳解

A、B、C、D

正確答案

若採用『中位數三數取樣(median-of-three)』作為pivot,已排序與反向排序皆為最佳情況O(N log N),隨機輸入平均也是O(N log N),故答案為(C)。

把隨機輸入寫成O(N²),錯誤;隨機輸入平均為O(N log N)。

載入中…

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