【圖解演算法教學】 還在用古老的二元搜尋法？是時候跟上「Hash Search」 的車尾燈了！ 封面圖：https://imgur.com/8GfYiTO 架構圖：https://imgur.com/SbC5IKY 在我們還沒學資料結構前，通常都用Linear Search找東西。 之後，我們學了二元樹，開始利用二元搜尋法，大幅提升搜尋效能。 然而，在演算法的世界中： 還有比Binary Search還快的東西，即是這次要介紹的「Hash Search」！ 影片連結：https://bit.ly/2Uv2sBf 影片章節含有： 00:00 開頭 00:02 Linear Search 00:58 Binary Search 02:38 Hash Search 04:38 結尾 [更新2020.11.25] 感謝版友們提供的建議，的確有地方我可以改進，這邊直接幫大家整理出重要內容： Linear Search : BigO(n) Binary Search : BigO(n) ~ BigO(log(n)) Hash Seach : BigO(n) ~ BigO(1) 可以看到，在最佳狀況下，Hash Search的效率是最快的，一步到位。 而之所以可以做到這樣的效能，是因為Hash Seach是by Index的搜尋方式。 比如說將 29 這個數字 經過hash之後： 9 = hash(29) 就能拿到 index 9 ，我們只要去查 array[9] == 29 是否正確，就能拿到結果。 當然，現實上沒這麼理想，會遇到「碰撞」，也就是不同來源數字hash到同一個index 這部分將在後續實作中介紹，這次主要是幫大家抓到使用「Hash Search」的誘因。 最後補充，Binary Search由於會先將資料排序，所以更適合用在「範圍搜尋」。 以上內容為影片重點萃取，有需要可以進一步參考影片完整介紹，感謝各位的建議！ -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 101.10.110.156 (臺灣) ※ 文章網址: https://webptt.cc/bbs/Tech_Job/M.1606205251.A.88E.html ※ 編輯: uopsdod (101.10.110.156 臺灣), 11/25/2020 07:04:10 ※ 編輯: uopsdod (101.10.110.156 臺灣), 11/25/2020 07:04:52 ※ 編輯: uopsdod (101.10.110.156 臺灣), 11/25/2020 07:05:56