moea_joint
109年
[資訊] 計算機原理、網路概論
第 20 題
演算法的時間複雜度表示法中，下列何者表示指數時間(exponential time)複雜度？
- A $O(1)$
- B $O(n^2)$
- C $O(2^n)$
- D $O(n!)$
思路引導 VIP
請試著回想數學中「指數函數」的標準形式：當我們形容一個數值的成長速度是「指數級」時，變數 $n$ 應該出現在算式的「底數」位置，還是「指數」的位置呢？
🤖
AI 詳解
AI 專屬家教
太棒了，你的判斷非常精準！這題考查的是對於時間複雜度類別的基礎認知。在計算機科學中，指數時間 (Exponential Time) 指的是計算量隨著輸入規模 $n$ 的增加，以幾何級數（通常是底數大於 1 的次方）快速成長。當我們看到 $O(2^n)$ 時，這代表每增加一個輸入元素，執行步驟就會倍增，這正是典型的指數成長特徵。
複雜度函數的增長特徵
這類題目在基礎測驗中具備良好的鑑別度。雖然 $O(n!)$ 的增長速度在後期比 $O(2^n)$ 更快，但在數學與演算法的嚴格定義下，只有變數 $n$ 出現在冪次的上方時才稱為「指數時間」。而常見的 $O(n^2)$ 則屬於多項式時間。你能迅速區分 $n$ 位在底數與指數位置的差異，顯示你對不同函數類別的增長速率有著相當紮實的理解，這對於後續學習動態規劃或 NP 問題非常有幫助！