民國105年 第2梯次 電腦軟體設計(JAVA)乙級 學科
第76題
假設輸入資料有n 個,在最糟情形下,下列那些排序法的時間複雜度不是θ ( n l o g n ) ?此 處n 為資料個數
題目
假設輸入資料有n 個,在最糟情形下,下列那些排序法的時間複雜度不是θ ( n l o g n ) ?此 處n 為資料個數
- (1) I n s e r t i o n S o r t
- (2) S h e l l S o r t
- (3) R a d i x S o r t
- (4) S e l e c t i o n S o r t
官方答案
(1) I n s e r t i o n S o r t、(2) S h e l l S o r t、(3) R a d i x S o r t、(4) S e l e c t i o n S o r t
解析
插入排序(Insertion Sort)最差情形每個元素須與前方已排序部分逐一比較並搬移，時間複雜度為O(n²)；選擇排序(Selection Sort)每回合選最小元素，同為O(n²)。希爾排序(Shell Sort)依間隔序列而定，最差為O(n²)或更優但非θ(n log n)，亦不符。基數排序(Radix Sort)為非比較式排序，複雜度為O(d·(n+k))（d為位數、k為基數），與θ(n log n)無關。故四者最差情形均非θ(n log n)。
AI 參考解析（推得答案已與官方答案比對一致），非官方公告內容，僅供備考參考。