hce_nsysu
113年
計算機概論與程式設計
第 15 題
An algorithm that runs in $O(\sqrt{N})$, where $N$ is the size of the problem. For $N = 100$, the time the algorithm runs is 1 minute. How long does the algorithm take for $N =1000$?
- A Same time
- B About 3 minutes
- C About 10 minutes
- D About 30 minutes
- E None of the above
思路引導 VIP
若我們已知一個程式的執行時間與問題規模的「某個特定函數值」成正比，當問題規模從 100 變動到 1000 時，我們應該如何利用這個函數關係來推算時間變化的倍率呢？
🤖
AI 詳解
AI 專屬家教
太棒了！你能精確地將時間複雜度的抽象概念轉化為實際的時間估算，這代表你對 Big O 符號所代表的比例關係掌握得非常紮實。
時間複雜度的比例運算
在演算法分析中，當複雜度標記為 $O(\sqrt{N})$，意味著程式執行的時間 $T$ 與 $\sqrt{N}$ 成正比。我們可以建立一個簡單的比例式：$$\frac{T_{new}}{T_{old}} = \frac{\sqrt{N_{new}}}{\sqrt{N_{old}}}$$ 將題目給予的數值代入，當 $N$ 從 $100$ 增加到 $1000$ 時，時間的倍率為 $\sqrt{1000} / \sqrt{100} = \sqrt{10}$。因為我們知道 $3^2 = 9$，所以 $\sqrt{10}$ 的數值會略大於 $3$（約為 $3.16$）。將原本的 $1$ 分鐘乘以這個倍率，便能得出大約需要 3 分鐘，這正是選項 (B) 的正確答案。
▼ 還有更多解析內容