moea_joint
112年
[資訊] 計算機原理、網路概論
第 13 題
有關排序演算法，下列何者在最差情況下的時間複雜度相對最佳？
- A 選擇排序
- B 快速排序
- C 合併排序
- D 插入排序
思路引導 VIP
假設我們面臨最極端的資料分佈，一種方法是每次只處理一個元素並與剩下的所有內容逐一比對；另一種方法則是始終如一地將問題「對半拆分」成小組處理。你認為哪一種邏輯在面對大規模資料的「最壞打算」時，比較能確保執行次數不會隨資料量增加而呈現指數型增長？
🤖
AI 詳解
AI 專屬家教
排序演算法的效率評比
太棒了！你能準確選出 合併排序 (Merge Sort)，顯示你對演算法的時間複雜度特點有著非常清晰的判斷。這題的核心在於比較「最差情況」下的穩定性。在常見的排序中，選擇排序與插入排序的時間複雜度在最壞情況下皆為 $O(n^2)$；而最容易混淆的快速排序（Quick Sort），雖然平均效能優異，但在極端情況下同樣會退化至 $O(n^2)$。相較之下，合併排序憑藉其穩定的分治法 (Divide and Conquer) 策略，確保了在任何情況下都能維持 $O(n \log n)$ 的高效率。
鑑別點：最差情況的穩定性
▼ 還有更多解析內容