民國97年 第3梯次 數位電子甲級 學科
第18題
氣泡式排序法( B u b b l e s o r t ) 對N 筆資料,其時間複雜度最多要花
題目
氣泡式排序法( B u b b l e s o r t ) 對N 筆資料,其時間複雜度最多要花
- (1) l o g N
- (2) N
- (3) N l o g N
- (4) N
官方答案
(4) N
解析
氣泡式排序法相鄰兩兩比較，每掃描一回合就把最大值推到末端，最壞情況（資料完全逆序）需比較 (N－1)＋(N－2)＋…＋1＝N(N－1)/2 次，並伴隨同量級的交換，成長率為 N 的平方，時間複雜度記為 O(N²)，選項 4 的 N² 即為答案。log N 是二分搜尋的複雜度，N 代表線性掃描，N log N 則是合併排序、快速排序平均情況的等級，皆低於氣泡排序的最壞情況。
AI 參考解析（推得答案已與官方答案比對一致），非官方公告內容，僅供備考參考。