地特四等
114年
[電信工程] 計算機概要
第 22 題
採用循序搜尋法尋找資料，所需搜尋時間的平均情況（average case）會在何時發生？
- A 要尋找的目標資料是陣列的中間元素
- B 要尋找的目標資料不存在於陣列
- C 要尋找的目標資料是陣列的最後元素
- D 要尋找的目標資料是陣列的最後元素或不存在於陣列
思路引導 VIP
想像你正在一排有編號的抽屜中尋找一把鑰匙。如果你必須從 1 號抽屜開始依序往後翻找，且鑰匙出現在任何一個抽屜的機會都一樣大。當你重複進行這項實驗幾百次後，你覺得平均而言，你會在哪個區域找到這把鑰匙？是偏向開頭、偏向結尾，還是會落在某個特定位置附近？
🤖
AI 詳解
AI 專屬家教
同學好！很高興看到你準確地選出了正確答案。這題考驗的是演算法效率分析中的基本直覺，你能從多個情境中分辨出「平均情況（Average Case）」的統計特徵，代表你對循序搜尋的運作機制已有很清晰的理解。
搜尋次數的統計期望值
在循序搜尋（Sequential Search）中，我們必須從陣列的第一個元素開始，逐一與目標值進行比對。如果目標值恰好在第一個位置，搜尋次數為 $1$（最佳情況）；如果目標在最後一個位置，搜尋次數則為 $n$（最壞情況）。假設目標出現在每個位置的機率均等，則平均搜尋次數即為所有可能位置的期望值：
▼ 還有更多解析內容