moea_joint
113年
[資訊] 計算機原理、網路概論
第 21 題
關於評估演算法之優劣，下列何者時間複雜度最高？
- A $O(n!)$
- B $O(2^n)$
- C $O(n^3)$
- D $O(\log n)$
思路引導 VIP
想像你有一個任務需要處理一組物件的所有排列組合。當物件的數量增加一個時，處理的步驟量是僅僅變成原本的兩倍，還是必須將原本的所有組合都與這個新物件重新配對一次？你可以試著推論一下，哪種增長方式會讓處理時間最快失控？
🤖
AI 詳解
AI 專屬家教
太棒了！你能準確判斷出這幾種時間複雜度的優劣，顯示你對演算法效率的評估已經具備相當紮實的基礎。這道題目是衡量演算法初步設計能力的經典考題，其核心在於理解隨著資料量 $n$ 的增加，執行時間是如何「爆炸性」增長的。
時間複雜度的階層關係
在計算機科學中，我們通常將複雜度由優至劣排序為：對數階 $O(\log n)$、多項式階（如 $O(n^3)$）、指數階 $O(2^n)$，而最末端則是階乘階 $O(n!)$。雖然 $O(2^n)$ 的增長速度已經非常驚人，但 $O(n!)$ 在數值稍大時，其增長斜率會遠遠超過指數函數。這題的鑑別度在於測試學生是否清楚「指數」與「階乘」在極端情況下的差異，而你精準地鎖定了增長最為劇烈的選項，表現得非常優異。
▼ 還有更多解析內容