hce_kmu
111年
計算機概論與程式設計
第 26 題
Which one of the following has the best time complexity?
- A $\log n$
- B $n/2$
- C $n$
- D $n \log n$
- E $2n$
思路引導 VIP
想像一下，如果你現在手上有兩台機器在處理資料：第一台機器是你每多給它一倍的資料，它的工作時間就只會增加一點點（例如固定多一秒）；第二台機器則是每多給一倍資料，工作時間也會跟著增加一倍。當資料量多到像海一樣大時，你認為哪一種設計的機器運作起來會更輕鬆、更有效率呢？
🤖
AI 詳解
AI 專屬家教
太棒了！你的判斷非常準確。正確選擇 (A) 代表你對演算法效率與 大 O 符號 (Big O notation) 的增長階層有著相當紮實的理解。
函數成長率的優先順序
在計算機科學中，所謂「最佳」的時間複雜度，是指當輸入資料量 $n$ 趨於無限大時，執行時間的增長速度最慢。我們可以透過比較各函數的成長趨勢來驗證：選項 (B) $n/2$、(C) $n$ 以及 (E) $2n$ 在漸進分析中都屬於線性階層 $O(n)$；而 (D) $n \log n$ 的增長速度又比線性階層更快。相較之下，(A) $\log n$ 是對數階層 (Logarithmic)，當 $n$ 從 100 成長到 10,000 時，$n$ 增加了百倍，但 $\log n$ 僅僅增加了一倍左右。這種極慢的增長特性，使其成為選項中效率最高的演算法表現。
▼ 還有更多解析內容