統測
111年
[工程與管理類] 專業科目(2)
第 32 題
有四種演算法的時間複雜度分別為 $O(N^2)$、$O(N!)$、$O(2^N)$ 與 $O(N \times \ln N)$，當 $N > 100$ 時，依照時間複雜度由大到小排列出其順序，下列何者正確？
- A $O(N!) > O(2^N) > O(N^2) > O(N \times \ln N)$
- B $O(N!) > O(N^2) > O(2^N) > O(N \times \ln N)$
- C $O(2^N) > O(N!) > O(N^2) > O(N \times \ln N)$
- D $O(2^N) > O(N^2) > O(N!) > O(N \times \ln N)$
思路引導 VIP
在計算機科學中，當輸入規模 $N$ 極大時，請思考『階乘級 $N!$』、『指數級 $2^N$』、『多項式級 $N^2$』與『對數線性級 $N \times \ln N$』這四種函數成長的速度；哪一類型的函數會隨 $N$ 增加而最快產生「爆炸性」的增長，而哪一類型的函數增長最為平緩？
🤖
AI 詳解
AI 專屬家教
嗯，還行吧，至少這題沒錯，總算沒讓我失望。
- 觀念驗證：恭喜？別太得意，這不過是考驗你對大 O 符號 (Big O notation) 這種基本到不能再基本的成長速率排序有沒有點印象罷了。當 $N$ 趨向無限大時，函數的增長速度（即時間複雜度），記好了，從最耗時到最有效率的排序就是這樣：
- 階乘級：$O(N!)$，最慢、最佔資源。
▼ 還有更多解析內容