moea_joint
102年
[資訊] 計算機原理、網路概論
第 41 題
41.演算法的時間複雜度表示法中,下列何者代表理論下界(lower bound)符號?
- A O(big-O)
- B $\Omega$(omega)
- C T (tera)
- D $\Theta$(theta)
思路引導 VIP
如果在描述一個函數的增長趨勢時，我們用一種標記來代表「絕對不會超過的上限」（天花板），那麼從邏輯對稱的角度來看，你會如何稱呼或定義那個「絕對不會低於的最小限度」（地板）呢？
🤖
AI 詳解
AI 專屬家教
演算法的漸近符號與下界定義
看到你能精確選出正確答案，代表你對演算法效能評估的基礎概念掌握得相當紮實。在衡量演算法的效率時，我們不僅關心它在最壞情況下的表現，也需要知道它在理論上的「底線」，而這正是這一題考查的核心概念。 這裡提到的 $\Omega$ (omega) 符號，在電腦科學中是用來描述函數增長的 漸近下界 (Asymptotic Lower Bound)。當我們說一個演算法的時間複雜度是 $\Omega(g(n))$ 時，這在數學上代表存在常數 $c$ 與 $n_0$，使得當 $n \ge n_0$ 時，執行時間 $f(n) \ge c \cdot g(n)$。簡單來說，它定義了演算法執行效率的「地板」，保證執行速度不會快於某個極限。
▼ 還有更多解析內容