假設以泡沫排序法（Bubble sort），將給定的n 個整數由小排到大，則該演算法執行數字比較的時間複雜度為下列何者？（注意：一次「數字比較」會比較兩個數字，…

題目

假設以泡沫排序法（Bubble sort），將給定的n 個整數由小排到大，則該演算法執行數字比較的時間複雜度為下列何者？（注意：一次「數字比較」會比較兩個數字，譬如：比較5 和3 何者較大。） A. O(1) B. O(n) C. O(nlogn) D. O(n2)

官方答案

• 答案：D. O(n2)

解析

泡沫排序（Bubble sort）對 n 個數由小排到大，第 1 回合比較 n−1 次、第 2 回合 n−2 次……直至第 n−1 回合比較 1 次，總比較次數 = (n−1)+(n−2)+…+1 = n(n−1)/2，故時間複雜度為 O(n²)，選 D。即便加入「某回合無交換即提前停止」的改良，最壞與平均情況仍是 O(n²)；最佳情況（已排序）比較次數約為 n−1 為 O(n)，但題目問一般比較次數仍以 O(n²) 表示。選項 C 的 O(n log n) 屬合併排序、堆積排序等較佳演算法，非泡沫排序。

AI 參考解析（推得答案已與官方答案比對一致），非官方公告內容，僅供備考參考。

官方資料

• 官方試題 PDF
• 官方答案 PDF

答案以考選部公告之測驗式試題標準答案 PDF 為準。