hce_nsysu
111年
計算機概論與程式設計
第 60 題
Which of the following statement about sorting algorithm is not true?
- A A sorting algorithm puts elements of a list into an order
- B For Quick sort, the average complexity is $n \log n$ to sort $n$ elements
- C For Bubble sort, the average complexity is $n^2$ to sort $n$ elements
- D For Insertion sort, the average complexity is $n^2$ to sort $n$ elements
- E For Selection sort, the average complexity is $n \log n$ to sort $n$ elements
思路引導 VIP
假設我們有一排雜亂的數字，如果我們規定每一步都必須「掃描過所有還沒排好序的數字」來找出最小的一個並放到正確位置，且這個動作要重複到所有位置都放對為止。請思考：隨著數字總量 $n$ 的增加，這種「每一輪都要看過剩餘所有數字」的特性，會讓總比較次數與 $n$ 呈現什麼樣的數學關係？
🤖
AI 詳解
AI 專屬家教
同學好！非常棒，你精確地辨識出了這題的錯誤敘述。這題的核心在於區別各類排序演算法在處理資料時的平均時間複雜度。在選項 (E) 中提到的選擇排序 (Selection Sort)，其運作邏輯是不論資料初始狀態為何，每一輪都必須掃描剩下的所有元素來找出極值，這意味著它包含了兩層嵌套迴圈，總比較次數會趨近於 $\frac{n(n-1)}{2}$。因此，它的平均複雜度應為 $O(n^2)$，而非像快速排序那樣高效的 $O(n \log n)$。
演算法效能與複雜度辨析
這道題目是資訊科學領域中非常基礎且具備鑑別度的練習，難度屬於 Easy。它要求學生不僅要理解演算法的定義（如選項 A），更要熟記幾種經典演算法——如快速排序 (Quick Sort)、氣泡排序 (Bubble Sort) 與插入排序 (Insertion Sort)——在效能表現上的差異。你能快速鎖定 (E) 為誤，代表你對 $O(n^2)$ 與 $O(n \log n)$ 兩大效能族群的分類掌握得相當紮實，這對於判斷程式效能與系統設計是非常關鍵的直覺。