普通考試
112年
[資訊處理] 計算機概要
第 5 題
一個演算法具有較低的複雜度（algorithm complexity），下列何者必然成立？
- A 在不同運算環境中都具有較佳效率
- B 問題規模趨近無限大時，比其他較高複雜度演算法所需步驟數目較少
- C 可以解決NP-hard的問題
- D 可以提供最佳結果（optimized solution）
思路引導 VIP
請試著思考：如果我們在評估兩套處理資料的方法，且完全不考慮哪台電腦跑得比較快。當我們要處理的資料量從『幾百筆』增加到『幾兆筆』時，我們最應該觀察的是哪一個指標，才能判斷誰在處理大規模問題時更具優勢？
🤖
AI 詳解
AI 專屬家教
太棒了！你的資訊科學直覺非常精準。
- 觀念驗證：演算法複雜度（Complexity）的核心在於漸進分析 (Asymptotic Analysis)。當我們說一個演算法具有「較低複雜度」時，通常是指其大 $O$ 符號的成長階數較低。雖然在資料量小或硬體不同時，低複雜度演算法未必比較快，但當問題規模 $n \to \infty$（趨近無限大）時，低複雜度的演算法其運算步驟的成長速度較慢，這正是「效能優勢」的本質定義。
- 難度點評：此題難度為 Medium。它成功鑑別了學生是否能區分「實際執行效率」與「理論時間複雜度」的差異。許多初學者會誤選 (A)，卻忽略了硬體常數與環境係數在複雜度分析中是被忽略的。
演算法複雜度定義
💡 複雜度衡量輸入規模趨近無限大時，資源消耗的漸近成長率。
| 比較維度 | 低複雜度演算法 (如 O(n)) | VS | 高複雜度演算法 (如 O(n²)) |
|---|---|---|---|
| 漸近成長率 | 線性增長，斜率固定 | — | 指數或平方增長，極快 |
| 小規模資料 | 優勢不明顯 | — | 可能因常數項較小而更快 |
| 大規模資料 | 執行步驟數顯著較少 | — | 執行步驟數呈爆發式成長 |
| 硬體環境影響 | 無關，屬演算法本質 | — | 無關，屬演算法本質 |
💬當問題規模 n 足夠大時，低複雜度演算法在效率上具備必然優勢。
