[心得] 圖解演算法 Hash Search有這麼快?(更新)
【圖解演算法教學】
還在用古老的二元搜尋法?是時候跟上「Hash Search」 的車尾燈了!
在我們還沒學資料結構前,通常都用Linear Search找東西。
之後,我們學了二元樹,開始利用二元搜尋法,大幅提升搜尋效能。
然而,在演算法的世界中:
還有比Binary Search還快的東西,即是這次要介紹的「Hash Search」!
影片章節含有:
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由於會先將資料排序,所以更適合用在「範圍搜尋」。
以上內容為影片重點萃取,有需要可以進一步參考影片完整介紹,感謝各位的建議!
--
空間換時間,跟我們肝換錢一樣
std都寫好寫滿了
講的沒有很深,建議看 wiki
unordered_map :
感謝分享 做的很好懂 很棒
讚 訂閱 分享
搜尋了id,相似東西一直重複po,洗文章?
奇怪 有人願意分享 不想看也不必要噓吧 是生活很不順嗎?
想來這騙流量膩 可惜我一次都沒點進去過
即使洗流量也無所謂,這種東西可以作為科普的入門阿,
如果什麼東西都說一次就會了,老師存在的價值就沒那麼
重要
上面真的一堆自覺很懂就不想複習的人呢
科普的東西很好啊 多讓台灣人瞭解科普知識是好事。 點一
次人家也賺不到0.1元
有人家裡不順就說人不順,家裡有人掛了嗎?
如果要傳遞知識,為什麼不把內容直接放在這篇文章,最後再
補充連結,達到傳遞與導流雙重目的。而是這篇只作為導流,
不順便放知識呢。建議原PO思考一下,達到目的有時有更好的
方法。不要只學那些低級的導流方法。
另外binary search與hash適用時機不同,標題過度誇張,講
的好像binary search很落後一樣,也讓人有不專業,或只為
了賺錢的觀感。建議以後也可更聰明的表達,讓自己更專業。
總覺得這些教學文用意良好,只是被一些低級的媒體影響了傳
遞知識的方式,蠻可惜的。
最後讀者的定位也很重要,想清楚這些內容誰看,自己與讀者
的價值會最大化呢。這時候內容的品質,以及引流的channel
會更精準,少了很多負面觀感。
期待更好的內容,真的。
有辦法用正反器兜出來
有時候做影片比較好懂 文字沒這麼好懂 這種艱澀知識類的
根本賺不到錢 真的沒必要這麼嚴苛 台灣網紅一堆垃圾影
片都幾百萬點閱 不是對台灣更糟嗎
樓上說奶台是垃圾????
........ 有個彈鋼琴沒露臉的居然1200萬點閱...
感謝原PO,的站內信回覆,真的是有心吧事情做得更好的人,
謝謝
推
噓的有什麼問題?不想看就滾
下這個標題大概不知道codeforces有很多題目
用hashmap會 timeout 用treemap反而可以AC
這個去軟體版比較合適吧
很簡單啊,因為這版叫tech job版,不是soft job 也不
是 student 版
發錯位置當然要噓
map: 紅黑樹(二元搜尋樹的一種特例
unordered_map: hash,使用上不需要知道次序的建議選第二
種
第一種比較快但佔空間
說真的 講的太淺 大概是給高中生認識計概的程度
衝流量啊嘻嘻
板主不處理這種和本板無關的文,到時候就一堆商業心得
分享廣告文洗板
你要創業那就po在創業板,po在這是在欠噓?
難得看到教學型文章,給推
這裡是半導體板
推
28
[限免] The Search【 遊 戲 名 稱 】:The Search 【限時/限量免費網址】: 【 介紹/商店連結 】:同上 【 領 取 條 件 】: 【 附 註 】:The Search : 4/15 1:00 結束20
Re: [討論] 演算法不強,還有辦法在資工混下去嗎?你好 是這樣的 在下也曾經迷失在Leetcode題海里 自己摸索了快半年 (= =) 才開始搞懂他的門路 摸索的過程中 還要搭配面試 最後才知道Leetcode到底在玩甚麼 其實最常考的 就是array/list/tree搭配BinarySearch/DFS/BFS 我敢說上面這六個東西佔據了線上測驗跟電話面試其中90%的題目13
Re: [新聞] 蘋果將偵測兒童色情影像 用戶上傳iCloud用檔案 hash 比對圖片實在太不可靠了,改個 1 bit 資料就可以讓 hash 不同 我覺得蘋果不會做這種智障系統,否則這系統根本沒用 所以去翻了一下相關文件 看起來是用蘋果自己開發的新演算法 NeuralHash7
Re: [問卦] 演算法DFS看得懂 但寫不出來 問題在哪?本巨巨推薦DFS從binary tree開始寫 並且要用遞迴的方式 用stack可以 但是全局視野比較沒有解子問題的感覺 類似這一題 98. Validate Binary Search Tree 這題就是要你驗證 這是不是一個Binary Search Tree5
Re: [新聞] 蘋果將偵測兒童色情影像 用戶上傳iCloud六七年前在讀研究所的時候,因為主題是影像分析比對,所以有找了許多論文 我就看過幾篇google 發表的論文 透過快速比對 hash 值來快速搜尋圖片 論文中就提到他們把 原先比較距離使用的 兩個值相減平方 這類的概念 直接改成把所有資料簡化成0與1 利用 OR XOR 的方法 來高速比對 當然 論文中並沒有提到 google 是如何對圖片做hash的 或是 用什麼方法取特徵點的3
[求救] 被search queuelocator.com綁架這幾天不知道載到了什麼 Chrome的搜尋引擎被強制替換成了search queuelocator 會強制跳到yahoo的頁面 沒辦法更換回原本的google搜尋引擎 試過了重灌chrome和用malwarebytes掃毒還是沒有用2
[課業] 計概問題請教想請教一題計概 103關務計概3等第二題 請教第二題的第二小題與第三小題 解答1
Re: [問卦] leetcode medium看完答案還是寫不出來千萬不要背的 原則上科技巨頭會避開網路上找得到的題目 之前被問的問題隔了五個月後才出現在leetcode 上面 要先熟悉基本的資料結構 hash map, stack, tree, trie,- 有在使用google analytics也要使用Google Search Console嗎? 學會使用GSC就能精準掌握使用者google的關鍵字! 這些關鍵字資料可是進入網站前使用者查詢的資料唷 這是GA看不到的重要資料Rrrrrr 資深SEO顧問 #孟令強 老師 2021重磅回歸
- 這題就是回答O(m+n) 面試官硬說不是線性 大概有以下幾種可能 1. 面試官搞錯order map跟unordered map了 2. 面試官想追問worst case的話 hash table的search複雜度就不是O(1) 這樣你的答案就不是O(m+n)