民國114年 第2梯次 電腦軟體設計(JAVA)乙級 學科
第22題
有三位學生各設計一個演算法解決同一個問題,並以兩組不同資料量進行測試,測試結果如下: (i)若資料量n 為10,第一位學生演算法之執行時間為1ms、第二位學生演…
題目
有三位學生各設計一個演算法解決同一個問題,並以兩組不同資料量進行測試,測試結果如下: (i)若資料量n 為10,第一位學生演算法之執行時間為1ms、第二位學生演算法之執行時間為 1/100ms、第三位學生演算法之執行時間為1/1000ms(ii),若資料量n 為100,第一位學生演算法 之執行時間為10ms、第二位學生演算法之執行時間為1ms、第三位學生演算法之執行時間為 1ms,下列敘述何者是正確的?
- (1) 第三位學生演算法之時間複雜度為O(n 2)
- (2) 當資料量n 小於 1000 時,第二位之學生演算法較具效率
- (3) 第一位學生演算法之時間複雜度為O(log n)
- (4) 第二位學生演算法之時間複雜度為O(n log n)
官方答案
(2) 當資料量n 小於 1000 時,第二位之學生演算法較具效率
解析
觀察資料量放大 10 倍時的成長：第一位由 1ms 變 10ms，同為 10 倍，複雜度為 O(n)；第二位由 0.01ms 變 1ms，放大 100 倍，約為 O(n²)；第三位由 0.001ms 變 1ms，放大 1000 倍，約為 O(n³)。故選項1（第三位為 O(n²)）、選項3（第一位為 O(log n)）、選項4（第二位為 O(n log n)）皆不符。第二位與第一位比較，令 n²/10000 < n/10，可得 n < 1000，即資料量小於 1000 時第二位較具效率，選項2正確。
AI 參考解析（推得答案已與官方答案比對一致），非官方公告內容，僅供備考參考。