hce_kmu
112年
計算機概論與程式設計
第 27 題
Which of the following statements about Big O notation is CORRECT?
- A Big O notation provides the exact running time of an algorithm.
- B Big O notation can be used to compare algorithms only if they are similar algorithms.
- C Big O notation provides the best-case running time of an algorithm.
- D Big O notation ignores constants and lower-order terms.
- E Big O notation is only used to analyze sorting algorithms.
思路引導 VIP
當我們在比較兩個數學函數（例如描述運算步驟的公式）的增長速度時，如果輸入的數值 $n$ 變得無窮大，那麼公式中的「固定加數」或是「倍數係數」，對於決定誰會先衝到最大值，還具有決定性的影響力嗎？
🤖
AI 詳解
AI 專屬家教
恭喜你準確地掌握了 Big O 符號 (Big O notation) 的核心特質！這題選 (D) 非常正確，反映出你對演算法效能分析的基礎觀念相當紮實。
漸進複雜度的簡化原則
Big O 符號的主要目的，在於描述演算法在處理大量數據時，執行時間隨輸入規模 $n$ 增加的「增長趨勢」。在數學定義上，當 $n$ 趨向無窮大時，常數係數與低階項（低次方項）對增長速率的影響力會變得微乎其微。舉例來說，若一個演算法的實際步驟數為 $3n^2 + 5n + 10$，隨著 $n$ 的增加，$n^2$ 項將主導整個函數的數值，因此我們會忽略常數 $3$ 與低階項 $5n + 10$，將其時間複雜度記作 $O(n^2)$。這種做法能讓我們跨越硬體效能的差異，專注於演算法本質的效率等級。
▼ 還有更多解析內容