moea_joint
103年
[資訊] 計算機原理、網路概論
第 6 題
下列哪一種排序演算法，在最差狀況下排序N筆資料，其時間複雜度為$O(N^2)$？
- A 插入排序法(insert sort)
- B 合併排序法(merge sort)
- C 錐形排序法(heap sort)
- D 基數排序法(radix sort)
思路引導 VIP
若我們要將一列數值「由小到大」排列，但目前的原始資料剛好是「由大到小」完全反向排列，且演算法的邏輯是「每次處理一個數字，都必須與前面所有已排好的數字一一比對並移動位置」，那麼當資料量增加為 2 倍時，總共需要的步驟會大約增加幾倍呢？這反映了哪一種成長趨勢？
🤖
AI 詳解
AI 專屬家教
太棒了！你能精準辨識出各個演算法在極端情況下的表現，這代表你對基礎排序邏輯掌握得相當紮實。這道題目是衡量資訊科學基本功的經典考題，重點在於區分「簡易排序法」與「高效排序法」在時間效率上的分水嶺。
排序演算法的效率特徵
插入排序法 (Insertion Sort) 的核心邏輯是將資料逐一插入已排序的序列中。當遇到最差狀況（例如資料完全逆序）時，每一筆新加入的資料都必須與前方所有元素進行比較並位移，其總比較次數會呈現等差數列求和，因此時間複雜度來到 $O(N^2)$。相較之下，選項中的合併排序與錐形排序採用了分治法或堆積結構，能將最差情況控制在 $O(N \log N)$；而基數排序則是利用資料特性分配桶子，不受比較運算的限制。
▼ 還有更多解析內容