12 表現複雜度時，下列那一個希臘文符號能表現出既不高於、也不低於參數所對應的複雜度等級？
(A) Ω(…)
(B) Ο(…)
(C) Φ(…)
(D) Θ(…)

答案：登入後查看
統計： A(25), B(80), C(47), D(110), E(0) #3429176

詳解 (共 2 筆)

#6761233
1. 題目解析 這道題目考察的是對於計算...
(共 749 字，隱藏中）
前往觀看
7
0
#6839462

答案是 (D) Θ(...)（Theta）

時間複雜度符號說明

Θ (Theta) - 緊確界（Tight Bound）✅

  • 既不高於、也不低於
  • 表示精確的複雜度等級
  • 同時是上界也是下界
  • 例如：Θ(n²) 表示複雜度恰好是 n² 等級

O (Big-O) - 上界（Upper Bound）

  • 表示不會超過某個複雜度
  • 只說明最壞情況
  • 例如：O(n²) 表示複雜度最多是 n² 等級
  • 可能實際更低（如 O(n) 也可以寫成 O(n²)）

Ω (Omega) - 下界（Lower Bound）

  • 表示至少需要某個複雜度
  • 只說明最好情況
  • 例如：Ω(n) 表示複雜度至少是 n 等級

Φ (Phi)

  • 這不是標準的複雜度符號
  • 可能是 φ（黃金比例）的誤植

圖解說明

O(n²) ← 上界（可能高估） ↑ Θ(n²) ← 精確界（恰好） ↓ Ω(n²) ← 下界（可能低估）

實例

假設某演算法實際複雜度是 n²：

✅ Θ(n²) 精確！ ✅ O(n²) 正確，但也可以寫 O(n³)（太寬鬆） ✅ Ω(n²) 正確，但也可以寫 Ω(n)（太寬鬆） ❌ Θ(n³) 錯誤，太高了 ❌ Θ(n) 錯誤，太低了

Θ 符號表示演算法的精確複雜度，既不會高估也不會低估！

ㅤㅤ
ㅤㅤ
ㅤㅤ
2
0