民國105年 第3梯次 電腦軟體應用乙級 學科
第15題
下列「排序演算法」中,哪一種的平均速度最快?
題目
下列「排序演算法」中,哪一種的平均速度最快?
- (1) 泡沫排序
- (2) 選擇排序
- (3) 插入排序
- (4) 快速排序
官方答案
(4) 快速排序
解析
比較平均時間複雜度：快速排序為 O(n log n)，泡沫排序、選擇排序、插入排序平均皆為 O(n²)。當資料量 n 增大時，n log n 的成長速度明顯低於 n²，例如 n=1000 時約 1000×10=10000 次運算量級，而 n² 為 1000000，差距懸殊。故平均速度最快者為快速排序。須注意快速排序最差情況會退化為 O(n²)，但題目問的是平均表現。
AI 參考解析（推得答案已與官方答案比對一致），非官方公告內容，僅供備考參考。