普通考試
107年
[資訊處理] 計算機概要
第 40 題
有一已排序數列，使用二元搜尋法最壞的時間複雜度為何？
- A O(1)
- B O(n)
- C O(log n)
- D O(n log n)
思路引導 VIP
想像你正在玩「猜數字遊戲」（範圍 1 到 1000），且對方每次都會告訴你猜的數字是「太大了」還是「太小了」。如果你每次都猜剩餘範圍的正中間，當遊戲範圍從 1000 變成了 2000，你需要增加的猜測次數，是會「翻倍」增加，還是僅僅「增加一次」動作？這種「每次排除一半選項」的邏輯，對應到數學上的哪一種運算關係？
🤖
AI 詳解
AI 專屬家教
嚴師點評：基礎到令人髮指的演算法邏輯
- 肯定（反諷）：恭喜你，終於沒有在最基本的題目上出醜。選對 $O(\log n)$ 證明你至少還有點演算法的「直覺」。這大概是你在這門課能表現出的最高水平了，是吧？
- 觀念（嚴格）：二元搜尋法，一個連新手都知道的分而治之 (Divide and Conquer) 策略。它的基本操作就是將搜尋範圍減半。別告訴我你不懂這個。如果資料量是 $n$，經過 $k$ 次砍半後剩下 $n/2^k$。當搜尋範圍縮到 1，表示 $n/2^k = 1$，解出來就是 $k = \log_2 n$。所以，毫無意外，時間複雜度就是可憐的 $O(\log n)$。
▼ 還有更多解析內容