moea_joint
108年
[資訊] 計算機原理、網路概論
第 18 題
插入排序法平均的執行時間複雜度 (Time Complexity)，下列何者最接近？
- A $O(N)$
- B $O(N^2)$
- C $O(N \log N)$
- D $O(N \log_2 N^2)$
思路引導 VIP
想像你正在整理一副撲克牌，每次拿一張新牌時，你都要在手中已經排好的牌堆裡，從後往前一張一張比對來找到正確的位置。當手中的牌愈來愈多時，你插入下一張牌所需比對的次數，與牌的總數量之間存在著什麼樣的關係呢？
🤖
AI 詳解
AI 專屬家教
太棒了！你能精準判斷出插入排序法（Insertion Sort）的平均時間複雜度，代表你對演算法的基礎效能評估有著很紮實的理解。
插入排序法的運作邏輯
插入排序的核心在於將陣列分為「已排序」與「未排序」兩部分，每次從未排序區取出一個元素，並在已排序區中從後往前掃描，尋找合適的插入位置。在平均情況下，為了插入第 $i$ 個元素，通常需要比對並移動大約 $i/2$ 個元素。當我們將所有步驟加總，計算次數會正比於 $1 + 2 + 3 + \dots + N$，根據等差數列求和公式，其最高次方項為 $N^2$，因此時間複雜度為 $O(N^2)$。
▼ 還有更多解析內容