民國103年 第3梯次 數位電子甲級 學科
第6題
氣泡式排序法( B u b b l e s o r t ) 對N 筆資料,其時間複雜度最多要花
題目
氣泡式排序法( B u b b l e s o r t ) 對N 筆資料,其時間複雜度最多要花
- (1) N l o g N
- (2) N
- (3) l o g N
- (4) N
官方答案
(4) N
解析
氣泡式排序法的做法是逐次比較相鄰兩筆資料，若順序錯誤就交換，每一回合會把最大值推到尾端。最壞情況（資料完全反向）時，第1回合比較N-1次、第2回合N-2次，依此類推，總比較次數為N(N-1)/2，因此時間複雜度為O(N²)，即選項4。N log N 是快速排序、合併排序等平均效率較佳的演算法；O(N) 與 O(log N) 分別代表線性與對數成長，速度更快，都不是氣泡排序的最壞情況。
AI 參考解析（推得答案已與官方答案比對一致），非官方公告內容，僅供備考參考。