申論題 - 阿摩線上測驗

申論題資訊

試卷：106年 - 106 經濟部所屬事業機構_新進職員甄試_資訊：1.資訊管理、2.程式設計#69345
科目：國營事業◆1.資訊管理 2.程式設計
年份：106年
排序：0

五、試以設計線上英文字典查詢的搜尋法為例，假設其資料分布均勻，請回答下列問題：（15 分）

(一)常見之搜尋法中，哪一種最適合應用此搜尋，且搜尋時間最有效率（3 分）？並請說明此搜尋法的時間複雜度（3 分）。

詳解提供者：Lin Jin

雖然參考書寫Binary Search，但我認為是Interpolation Search 最有效率，因為對於Interpolation Search來說，在資料是完美均勻的斜率(ith-data, data value )狀況下，他可以在第一步就找到目標。

詳解提供者：金榜題名阿罵頌

模糊

詳解提供者：我還有明天

循序搜尋法

時間複雜度O(1)

說明：

該英文字典以英文單辭字首

按abc…xyz 排序

搜尋某單辭時

直接對照其字首之字母

便可查詢到