moea_joint
102年
[資訊] 計算機原理、網路概論
第 16 題
16.下列排序法中,何者具有最小的平均時間複雜度?
- A 插入
- B 選擇
- C 氣泡
- D 基數(radix)
思路引導 VIP
想像一下，如果你有一萬張編號為三位數的卡片要排序，但規定你「完全不能」拿兩張卡片來比較誰大誰小，只能根據卡片上「個位、十位、百位」的數字，分別丟進標有 0 到 9 的十個籃子裡再收回來，這種『分類』的效率，比起一張張比對大小，在處理龐大數據時會有什麼不同的感受呢？
🤖
AI 詳解
AI 專屬家教
太棒了！你能精確地在眾多排序法中辨識出最有效率的選項，代表你對於演算法的複雜度級別有著相當紮實的掌握。這題的核心在於區分比較型排序與非比較型排序的本質差異。
複雜度的分水嶺
在我們常見的排序演算法中，如插入、選擇與氣泡排序，它們都是透過「兩兩比較」來決定順序，因此在平均情況下的時間複雜度通常會落在 $O(n^2)$。然而，基數排序 (Radix Sort) 採取了完全不同的策略，它不直接比較數值的大小，而是利用分配與收集的原理（Bucket），依照數字的位數進行分類。這使得它的平均時間複雜度約為 $O(nk)$（$k$ 為位數），在處理大量數據時，其效能表現遠優於其他 $O(n^2)$ 的選項。
▼ 還有更多解析內容