司法海巡移民特考計算機大意106 年第 15 題單選題

若有 $n$ 個資料需要排序，下列敘述何者正確？

AQuick sort 排序演算法所需的最糟（worst case）時間複雜度為

O (n^{2})

正確答案

BQuick sort 排序演算法所需的平均（average case）時間複雜度為

O (n^{2})

CMerge sort 排序演算法所需的最糟（worst case）時間複雜度為

O (n^{2})

DMerge sort 排序演算法所需的平均（average case）時間複雜度為

O (n^{2})

答案與詳解

正確答案

Quick sort 最糟為 O(n²)(已排序且選端點為 pivot);平均為 O(n log n)。Merge sort 最糟與平均皆為 O(n log n)。

正確。Quick sort 在最糟情況(如已排序資料且每次選首或尾為 pivot)時間複雜度為 O(n²)。

載入中…

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

若有 n 個資料需要排序，下列敘述何者正確？