10.若某演算法的時間複雜度是 O(n²)，代表什麼意思？
(A)執行時間與資料量無關
(B)執行時間與 n 的平方成正 比
(C) 執行時間會比 O(n) 演算法更快
(D)執行時間一定 比 O(n log n) 好 

答案：登入後查看
統計： A(0), B(16), C(2), D(1), E(0) #3678241

詳解 (共 1 筆)

#7222457

【解題思路】

先抓關鍵字：「時間複雜度 O(n²）」「代表什麼意思」。

在演算法中：

O(n²) 的意思就是：
如果資料量（n）變大，演算法的執行時間大約會跟 n 的平方 一樣成長。

例如 n 變 2 倍 → 執行時間變 4 倍
n 變 10 倍 → 執行時間變 100 倍

所以只有選項 (B) 完全符合定義。

【為什麼其他選項不正確？（逐一破題）】

(A) 執行時間與資料量無關

完全錯。
O(n²) 就是在描述「執行時間會隨著資料量 n 的變大而變慢」。

(B) 執行時間與 n 的平方成正比

正確！
O(n²) 就是 quadratic time（平方時間），
常見於：Bubble Sort、Selection Sort、Insertion Sort（平均）。

(C) 執行時間會比 O(n) 演算法更快

錯。
O(n) 比 O(n²) 快非常多。
O(n²) 通常是慢的演算法。

(D) 執行時間一定比 O(n log n) 好

錯。
O(n log n) 在資料量大時速度遠遠優於 O(n²)。

例如 n = 1,000：

  • n² = 1,000,000

  • n log n ≈ 10,000

差 100 倍以上。

【延伸知識（超常考）】

常見時間複雜度由快到慢（給你記憶順序）：

  1. O(1) 常數時間

  2. O(log n) 對數

  3. O(n) 線性

  4. O(n log n) 分治法（如 Merge Sort）

  5. O(n²) 平方級（最常考的慢）

  6. O(2ⁿ) 指數

  7. O(n!) 階乘（非常慢）

O(n²) 通常代表演算法有「雙層迴圈」或「兩兩比較」。

【記憶技巧】

口訣：
「平方級 n²，資料多就崩潰。」
「n 加倍，時間變 4 倍。」

或：

O(n²) = 雙層迴圈的代名詞。

【常見錯誤】

  1. 以為 O(n²) 比 O(n log n) 快 → 完全相反

  2. 以為 O(n²) 跟資料量無關 → 錯，複雜度就是「資料量的影響」

  3. 把「最差」與「平均」複雜度混成一個（本題沒考，但常出現）

0
0