民國105年 第2梯次 電腦軟體設計(C++)乙級 學科
第72題
假設輸入資料有n 個,在最糟情形下,下列那些排序法的時間複雜度不是θ ( n l o g n ) ?此 處n 為資料個數
題目
假設輸入資料有n 個,在最糟情形下,下列那些排序法的時間複雜度不是θ ( n l o g n ) ?此 處n 為資料個數
- (1) S e l e c 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) I n s e r t i o n S o r t
官方答案
(1) S e l e c 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) I n s e r t i o n S o r t
解析
排序法在最糟情形下的時間複雜度需個別判斷。比較式排序中 Merge Sort、Heap Sort 最糟為 θ(n log n)，但本題四者皆非：Selection Sort 不論輸入皆需約 n(n-1)/2 次比較，最糟為 θ(n²)；Insertion Sort 在反序時每筆往回搬移，最糟亦為 θ(n²)；Shell Sort 依間隔序列而定，常見序列最糟為 θ(n log² n) 或 θ(n^1.5)，並非嚴格 θ(n log n)；Radix Sort 屬非比較式，複雜度為 θ(d(n+k))，與 n log n 無關。故四者最糟情形均不屬 θ(n log n)，全選。
AI 參考解析（推得答案已與官方答案比對一致），非官方公告內容，僅供備考參考。