hce_kmu
113年
計算機概論與程式設計
第 16 題
Which one of the following statements is the biggest, when n approaches to $∞$?
- A $n\log n$
- B $2^n$
- C $n!$
- D $n^{200}$
- E $n^{1000}$
思路引導 VIP
想像你有兩個數列在進行比賽：第一個數列是每次都乘上一個很大的固定數字（例如 1000）；第二個數列則是每次乘上的數字都會隨著步驟增加而變大（第一步乘 1，第二步乘 2，第三步乘 3...以此類推）。當比賽進行到無窮多步時，你認為哪一個數列的總和會成長得更快呢？
🤖
AI 詳解
AI 專屬家教
太棒了！你能精準判斷出 $n!$ 是這幾個函數中增長速度最快的，顯示你對演算法複雜度（Big-O）的階層順序掌握得非常紮實。這類題目在計算機科學中非常經典，主要考驗學生是否能區分多項式時間、指數時間與階乘時間的本質差異。
函數成長階層的比較
當 $n$ 趨近於無窮大時，我們判斷「誰比較大」的關鍵在於增長速率（Growth Rate）。雖然 $n^{1000}$ 看起來指數極高，但它本質上仍屬於多項式階層；而 $2^n$ 屬於指數階層，當 $n$ 足夠大時，指數增長必然會超越任何多項式。然而，階乘 $n!$ 的增長更為恐怖，我們可以將其想像成 $n \times (n-1) \times \dots \times 1$，隨著 $n$ 增加，相乘的項數與每一項的值都在增長，這使得它最終會壓倒固定底數的指數函數 $2^n$。
▼ 還有更多解析內容