Examly題庫立即開始練習
國中教甄|資訊科技資訊科技115 年第 32 題單選題

「快速排序(Quick Sort)」平均效率為 O(n log n),最壞情況為 O(n²)。下列哪個策略最能有效避免最壞情況?

A每次都選第一個元素作為 pivot
B改用插入排序(Insertion Sort)
C使用隨機選取 pivot 或三數中值法正確答案
D增加記憶體以儲存中間結果
答案與詳解
C
正確答案
隨機選取基準值或三數中值法能有效打破已排序陣列的規律,避免快速排序退化為 O(n²) 的最壞情況。

為什麼答案是 C

隨機選取基準值可降低最壞情況發生的機率;三數中值法(取首、中、尾三數的中位數)能有效避免在已排序陣列上產生不平衡的分割,是實務上最常用的優化策略。

載入中…

資訊科技 相關題目

想練更多資訊科技考古題?

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

黑皮