民國105年 第2梯次 數位電子甲級 學科
第52題
氣泡式排序法( B u b b l e s o r t ) 對N 筆資料,其時間複雜度最多要花
題目
氣泡式排序法( B u b b l e s o r t ) 對N 筆資料,其時間複雜度最多要花
- (1) N
- (2) l o g N
- (3) N
- (4) N l o g N
官方答案
(3) N
解析
氣泡排序法（Bubble Sort）對N筆資料，最壞情況（資料完全反向）需進行N-1回合，第i回合比較N-i次，總比較次數約為N(N-1)/2，故時間複雜度為O(N²)。選項1(N)、2(logN)、4(NlogN)皆非最壞情況的成長級數，正確為選項3（N²）。氣泡排序平均與最壞情況皆為O(N²)，僅當資料已排序且加入交換旗標改良時，最佳情況可達O(N)。
AI 參考解析（推得答案已與官方答案比對一致），非官方公告內容，僅供備考參考。