民國111年 第3梯次 數位電子甲級 學科
第22題
氣泡式排序法(Bubble sort)對N 筆資料,其時間複雜度最多要花
題目
氣泡式排序法(Bubble sort)對N 筆資料,其時間複雜度最多要花
- (1) Nlog 2 N
- (2) N
- (3) N2
- (4) log 2 N
官方答案
(3) N2
解析
氣泡排序法每一回合由頭到尾兩兩比較相鄰元素，必要時交換，一回合可把最大值推到尾端。N 筆資料最多需進行 N−1 回合，每回合比較次數最多約 N−1 次，總比較次數約為 N(N−1)/2，取最高次項後時間複雜度為 O(N²)，因此最多要花 N²。Nlog₂N 是先進排序法（如合併排序、快速排序平均）的等級，log₂N 對應二分搜尋，N 則是線性掃描。
AI 參考解析（推得答案已與官方答案比對一致），非官方公告內容，僅供備考參考。