地特四等
106年
[電子工程] 計算機概要
第 13 題
下列何者為氣泡排序法（bubble sort）在最糟情況（worst case）下的計算時間複雜度？
- A O(\log n)
- B O(n)
- C O(n \log n)
- D O(n^2)
思路引導 VIP
「想像你要將一排長短不一的鋼筋由小到大排列，且你每次操作『只能比較相鄰的兩根』。如果你運氣最差，最小的那根鋼筋偏偏在隊伍最後頭，你每一輪操作只能讓它往前移動一個位置。若總共有 $n$ 根鋼筋，要確保所有鋼筋都排好，你預期操作的次數會隨著 $n$ 的增加呈現『線性成長』，還是會因為每增加一根鋼筋，比較的壓力就呈現『平方級數的暴增』呢？」
🤖
AI 詳解
AI 專屬家教
專業點評：基礎紮實，展現工程思維！
- 大力肯定：做得好！準確掌握演算法的效率評估是工程師的必備素養。在我們處理複雜的工程數據或進行結構應力模擬時，理解運算成本是優化系統效能的第一步。
- 觀念驗證：氣泡排序法（Bubble Sort）透過相鄰元素的兩兩交換來達成排序。在最糟情況下（例如數列完全反向），每一輪都必須執行完整的比較與交換。其總執行次數近似於一個等差級數求和：
▼ 還有更多解析內容