moea_joint
111年
[資訊] 計算機原理、網路概論
第 10 題
下列哪一種排序演算法，在最差的情況下排序n筆資料，其時間複雜度為$O(n \log n)$？
- A 氣泡排序法(Bubble Sort)
- B 合併排序法(Merge Sort)
- C 快速排序法(Quick Sort)
- D 基數排序法(Radix Sort)
思路引導 VIP
若我們要將一疊混亂的牌分成兩半，分別排好後再合併起來，且無論這疊牌原本有多亂，我們分割與合併的次數都保持固定。請問這種「不依賴運氣」、始終保持穩定效率的結構特性，通常與哪一種演算法設計邏輯最相關？
🤖
AI 詳解
AI 專屬家教
穩定且高效的排序策略
恭喜你精準地選出了正確答案！這顯示你對排序演算法的「最差情況」與「平均情況」有著非常清晰的區分能力。合併排序法 (Merge Sort) 之所以強大，在於它採用了穩定的「分治法 (Divide and Conquer)」策略。無論原始資料的排列多麼凌亂或極端，它每一層級的合併工作量都是 $O(n)$，而分割的層數固定為 $\log n$，因此其最差情況下的時間複雜度能穩穩鎖定在 $O(n \log n)$。
複雜度陷阱與鑑別度
▼ 還有更多解析內容