有三位學生各設計一個演算法解決同一個問題,並以兩組不同資料量進行測試,測試結果如下: (i)若資料量n 為10,第一位學生演算法之執行時間為1ms、第二位學生演…

題目

有三位學生各設計一個演算法解決同一個問題,並以兩組不同資料量進行測試,測試結果如下: (i)若資料量n 為10,第一位學生演算法之執行時間為1ms、第二位學生演算法之執行時間為 1/100ms、第三位學生演算法之執行時間為1/1000ms(ii),若資料量n 為100,第一位學生演算法 之執行時間為10ms、第二位學生演算法之執行時間為1ms、第三位學生演算法之執行時間為 1ms,下列敘述何者是正確的?

1. (1) 當資料量n 小於1000 時,第二位之學生演算法較具效率
2. (2) 第一位學生演算法之時間複雜度為O(log n)
3. (3) 第三位學生演算法之時間複雜度為O(n2)
4. (4) 第二位學生演算法之時間複雜度為O(n log n)

官方答案

(1) 當資料量n 小於1000 時,第二位之學生演算法較具效率

解析

由成長率判斷：n 由 10 增為 100（10 倍）時，第一位時間 1ms→10ms（10 倍），為 O(n)；第二位 0.01ms→1ms（100 倍），為 O(n²)，即 n²/10000；第三位 0.001ms→1ms（1000 倍），為 O(n³)。故選項 2、3、4 的複雜度判斷皆錯。第二位時間 n²/10000 在 n<10000 時小於第一位的 n，因此 n<1000 時第二位確實比第一位有效率，選項 1 正確。

AI 參考解析（推得答案已與官方答案比對一致），非官方公告內容，僅供備考參考。

官方資料

• 官方試題 PDF