民國112年 第3梯次 數位電子甲級 學科
第51題
氣泡式排序法(Bubble sort)對N 筆資料,其時間複雜度最多要花
題目
氣泡式排序法(Bubble sort)對N 筆資料,其時間複雜度最多要花
- (1) N 2
- (2) N
- (3) Nlog 2 N
- (4) log 2 N
官方答案
(1) N 2
解析
氣泡式排序法最壞情況發生在資料完全反向時：第一回合比較 N-1 次，第二回合 N-2 次，依此類推，總比較次數為 (N-1)+(N-2)+…+1＝N(N-1)/2，最高次項為 N^2，因此時間複雜度為 O(N^2)。Nlog2N 是合併排序等較有效率演算法的量級。
AI 參考解析（推得答案已與官方答案比對一致），非官方公告內容，僅供備考參考。