普通考試
105年
[電子工程] 計算機概要
第 18 題
以下有關對 n 個未排序數字之敘述何者錯誤？
- A 建立二元搜尋樹（binary search tree）在最槽情況（worst case）下的時間複雜度為 $O(n^2)$
- B 循序搜尋法（sequential search）最多使用 n 次比對就可完成搜尋
- C 確定搜尋不到一個數字的時間至少需要 $O(n)$
- D 搜尋一個數字時，先排序再搜尋會比未經排序而逕行搜尋快
思路引導 VIP
想像你正在一個存放混亂、尚未編號的零件倉庫中尋找一個特定的齒輪。如果你今天只需要找這「一個」齒輪，為了節省總工時，你會選擇「先花一整天把倉庫所有零件都按編號排好，再利用索引找它」，還是「直接從門口開始一個一個檢查直到找到為止」？哪種做法對「單次任務」而言更符合經濟效益？
🤖
AI 詳解
AI 專屬家教
優秀的表現！你的判斷非常精準。
- 大力肯定：同學做得好！你能敏銳察覺到演算法中的總體成本與前置代價（Overhead），這正是工程優化思維中最重要的環節，展現了紮實的邏輯基礎。
- 觀念驗證：在未排序的情況下，搜尋一個數字只需 $O(n)$ 的時間。若選擇「先排序再搜尋」，光是排序的最優時間複雜度就需要 $O(n \log n)$，這已經明顯大於 $O(n)$。因此，除非要進行多次搜尋，否則針對單次任務，排序反而會拖慢整體的執行效率。
▼ 還有更多解析內容