Q182.
有三位學生各設計一個演算法解決同一個問題，並以兩組不同資料量進行測試，測試結果如下：(i)若資料量n 為10，第一位學生演算法之執行時間為1ms、第二位學生演算法之執行時間為1/100ms、第三位學生演算法之執行時間為1/1000ms(ii)，若資料量n 為100，第一位學生演算法之執行時間為10ms、第二位學生演算法之執行時間為1ms、第三位學生演算法之執行時間為1ms，下列敘述何者是正確的？
電腦軟體設計共同科目 · 乙級 · Q182
難易度分析
3 / 5
本題需要將實測數據與時間複雜度的成長率進行對比分析，要求考生能獨立推導資料量變化與執行時間之間的倍數關係，並在多個複雜度選項中進行排除與比較。
正確答案：④當資料量n 小於1000 時，第二位之學生演算法較具效率
④ 當資料量n 小於1000 時，第二位之學生演算法較具效率:根據測試數據，當 n=10 時第二位學生僅需 1/100ms（最快），當 n=100 時第二位與第三位均為 1ms。推導可知第二位為 O(n²)、第三位為 O(n³)，在 n<1000 的範圍內，O(n²) 的執行時間始終優於 O(n³)，故此敘述正確。
錯誤選項解析
- ① 第一位學生演算法之時間複雜度為O(log n):第一位學生當 n 從 10 增至 100（10倍）時，執行時間從 1ms 增至 10ms（10倍），呈現線性成長關係，故其時間複雜度應為 O(n)，而非 O(log n)。O(log n) 的特徵是資料量倍增時執行時間僅增加固定量。
- ② 第二位學生演算法之時間複雜度為O(n log n):第二位學生當 n 從 10 增至 100（10倍）時，執行時間從 1/100ms 增至 1ms（100倍），呈現平方級成長關係，故其時間複雜度應為 O(n²)，而非 O(n log n)。O(n log n) 的成長速率介於線性與平方之間。
- ③ 第三位學生演算法之時間複雜度為O(n 2):第三位學生當 n 從 10 增至 100（10倍）時，執行時間從 1/1000ms 增至 1ms（1000倍），呈現立方級成長關係，故其時間複雜度應為 O(n³)，而非 O(n²)。O(n²) 在資料量10倍時執行時間應為100倍。
Learning Tip
"本題核心考點為時間複雜度的實測推導法：比較資料量變化倍率與執行時間變化倍率的關係。若資料量增 k 倍，時間增 k 倍則為 O(n)、增 k² 倍則為 O(n²)、增 k³ 倍則為 O(n³)。常考陷阱是僅看絕對執行時間而忽略成長趨勢，小資料量時 O(n³) 可能因常數項小而較快，但大資料量時低階複雜度必然勝出。實務上應以漸進分析而非單一測試點判斷演算法優劣。"
學員答題分佈
①第一位學生演算法之時間複雜度為O(log n)0%
②第二位學生演算法之時間複雜度為O(n log n)0%
③第三位學生演算法之時間複雜度為O(n 2)0%
④當資料量n 小於1000 時，第二位之學生演算法較具效率0%
此答題分佈是根據學員在 LongePass 模擬考等實際作答紀錄計算而成。與考友分享這道歷屆試題與詳細解析！
