在計算機發展飛速的今天,也許有人會問,「今天計算機這麼快,算法還重要嗎?」其實永遠不會有太快的計算機,因為我們總會想出新的應用。雖然在摩爾定律的作用下,計算機的計算能力每年都在飛快增長,價格也在不斷下降。可我們不要忘記,需要處理的信息量更是呈指數級的增長。現在每人每天都會創造出大量數據。日益先進的紀錄和存儲手段使我們每個人的信息量都在爆炸式的增長。網際網路的信息流量和日誌容量也在飛快增長。在科學研究方面,隨著研究手段的進步,數據量更是達到了前所未有的程度。無論是三維圖形、海量數據處理、機器學習、語音識別,都需要極大的計算量。在網絡時代,越來越多的挑戰需要靠卓越的算法來解決。
總之,算法是計算機科學領域最重要的基石之一,算法工程師也是數據科學領域最重要的崗位之一,對於一些只掌握新的語言、技術、標準而不掌握算法的小夥伴,是不可能成為高手的。因此,今天我們整理出一些經典算法以及相關學習資源,歡迎大家收藏並轉發哦。
1、排序算法
冒泡算法
冒泡排序,有時也稱為下沉排序,是一種簡單的排序算法,它反覆遍歷要排序的列表,比較每對相鄰的項目,如果它們的順序錯誤則交換它們。重複傳遞列表,直到不需要交換,這表明列表已排序。
用python代碼實現:
https://www.toptal.com/developers/sorting-algorithms/bubble-sort
歸併排序
歸併排序(Merge sort,或mergesort),是創建在歸併操作上的一種有效的排序算法,。1945年由約翰·馮·諾伊曼首次提出。該算法是採用分治法(Divide and Conquer)的一個非常典型的應用,且各層分治遞歸可以同時進行。
用python代碼實現:
https://www.toptal.com/developers/sorting-algorithms/merge-sort
雞尾酒排序
雞尾酒排序,也叫雙向冒泡排序(Bidirectional Bubble Sort)等。這是冒泡排序的一種變體。不同之處在於,冒泡排序是從低到高比較序列裡的每個元素,而雞尾酒排序從兩個方向(低到高、高到低)來回排序,效率更高。
用python代碼實現:
https://en.wikipedia.org/wiki/Cocktail_shaker_sort
插入排序
插入排序(英語:Insertion Sort)是一種簡單直觀的排序算法。它的工作原理是通過構建有序序列,對於未排序數據,在已排序序列中從後向前掃描,找到相應位置並插入。插入排序在實現上,通常採用in-place排序,因而在從後向前掃描過程中,需要反覆把已排序元素逐步向後挪位,為最新元素提供插入空間。
用python代碼實現:
https://www.toptal.com/developers/sorting-algorithms/insertion-sort
快速排序
快速排序(英語:Quicksort),又稱劃分交換排序(partition-exchange sort),簡稱快排,最早由Tony Hoare爵士設計,它的基本思想是將待排序列分為兩半,左邊的一半總是「小的」,右邊的一半總是「大的」,這一過程不斷遞歸持續下去,直到整個序列有序。說起這位Tony Hoare爵士,快速排序算法其實只是他不經意間的小小發現而已,他對於計算機貢獻主要包括形式化方法理論,以及ALGOL60 程式語言的發明等,他也因這些成就獲得1980 年圖靈獎。
用python代碼實現:
https://www.toptal.com/developers/sorting-algorithms/quick-sort
堆排序
堆排序(英語:Heapsort)是指利用堆這種數據結構所設計的一種排序算法。堆是一個近似完全二叉樹的結構,並同時滿足堆積的性質:即子節點的鍵值或索引總是小於(或者大於)它的父節點。
用python代碼實現:
https://www.toptal.com/developers/sorting-algorithms/heap-sort
歸併排序
歸併排序(英語:Merge sort,或mergesort),是創建在歸併操作上的一種有效的排序算法,。1945年由約翰·馮·諾伊曼首次提出。該算法是採用分治法(Divide and Conquer)的一個非常典型的應用,且各層分治遞歸可以同時進行。
用python代碼實現:
https://www.toptal.com/developers/sorting-algorithms/merge-sort
選擇排序
選擇排序(Selection sort)是一種簡單直觀的排序算法。它的工作原理如下。首先在未排序序列中找到最小(大)元素,存放到排序序列的起始位置,然後,再從剩餘未排序元素中繼續尋找最小(大)元素,然後放到已排序序列的末尾。以此類推,直到所有元素均排序完畢。
用python代碼實現:
https://www.toptal.com/developers/sorting-algorithms/selection-sort
希爾排序
希爾排序,也稱遞減增量排序算法,是插入排序的一種更高效的改進版本。希爾排序是非穩定排序算法。希爾排序是基於插入排序的以下兩點性質而提出改進方法的:插入排序在對幾乎已經排好序的數據操作時,效率高,即可以達到線性排序的效率;但插入排序一般來說是低效的,因為插入排序每次只能將數據移動一位。
用python代碼實現:
https://www.toptal.com/developers/sorting-algorithms/shell-sort
2、搜索算法
二分查找算法
二分查找算法是一種在有序數組中查找某一特定元素的搜索算法。搜素過程從數組的中間元素開始,如果中間元素正好是要查找的元素,則搜素過程結束;如果某一特定元素大於或者小於中間元素,則在數組大於或小於中間元素的那一半中查找,而且跟開始一樣從中間元素開始比較。如果在某一步驟數組為空,則代表找不到。這種搜索算法每一次比較都使搜索範圍縮小一半。折半搜索每次把搜索區域減少一半,時間複雜度為Ο(logn) 。
BFPRT(線性查找算法)
BFPRT算法解決的問題十分經典,即從某n個元素的序列中選出第k大(第k小)的元素,通過巧妙的分析,BFPRT可以保證在最壞情況下仍為線性時間複雜度。
算法步驟:
1.將n個元素每5個一組,分成n/5(上界)組。
2.取出每一組的中位數,任意排序方法,比如插入排序。
3.遞歸的調用selection算法查找上一步中所有中位數的中位數,設為x,偶數個中位數的情況下設定為選取中間小的一個。
4.用x來分割數組,設小於等於x的個數為k,大於x的個數即為n-k。
5.若i==k,返回x;若i<k,在小於x的元素中遞歸查找第i小的元素;若i>k,在大於x的元素中遞歸查找第i-k小的元素。
終止條件:n=1時,返回的即是i小元素。
DFS(深度優先搜索)
深度優先搜索算法(Depth-First-Search),是搜索算法的一種。它沿著樹的深度遍歷樹的節點,儘可能深的搜索樹的分支。當節點v的所有邊都己被探尋過,搜索將回溯到發現節點v的那條邊的起始節點。這一過程一直進行到已發現從源節點可達的所有節點為止。如果還存在未被發現的節點,則選擇其中一個作為源節點並重複以上過程,整個進程反覆進行直到所有節點都被訪問為止。DFS屬於盲目搜索。
深度優先搜索是圖論中的經典算法,利用深度優先搜索算法可以產生目標圖的相應拓撲排序表,利用拓撲排序表可以方便的解決很多相關的圖論問題,如最大路徑問題等等。一般用堆數據結構來輔助實現DFS算法。
深度優先遍歷圖算法步驟:
1.訪問頂點v;
2.依次從v的未被訪問的鄰接點出發,對圖進行深度優先遍歷;直至圖中和v有路徑相通的頂點都被訪問;
3.若此時圖中尚有頂點未被訪問,則從一個未被訪問的頂點出發,重新進行深度優先遍歷,直到圖中所有頂點均被訪問過為止。
上述描述可能比較抽象,舉個實例:
DFS在訪問圖中某一起始頂點v後,由v出發,訪問它的任一鄰接頂點w1;再從w1出發,訪問與w1鄰接但還沒有訪問過的頂點w2;然後再從w2出發,進行類似的訪問,…如此進行下去,直至到達所有的鄰接頂點都被訪問過的頂點u為止。
接著,退回一步,退到前一次剛訪問過的頂點,看是否還有其它沒有被訪問的鄰接頂點。如果有,則訪問此頂點,之後再從此頂點出發,進行與前述類似的訪問;如果沒有,就再退回一步進行搜索。重複上述過程,直到連通圖中所有頂點都被訪問過為止。
BFS(廣度優先搜索)
廣度優先搜索算法(Breadth-First-Search),是一種圖形搜索算法。簡單的說,BFS是從根節點開始,沿著樹(圖)的寬度遍歷樹(圖)的節點。
如果所有節點均被訪問,則算法中止。BFS同樣屬於盲目搜索。一般用隊列數據結構來輔助實現BFS算法。
算法步驟:
1.首先將根節點放入隊列中。
2.從隊列中取出第一個節點,並檢驗它是否為目標。如果找到目標,則結束搜尋並回傳結果。否則將它所有尚未檢驗過的直接子節點加入隊列中。
3.若隊列為空,表示整張圖都檢查過了——亦即圖中沒有欲搜尋的目標。結束搜尋並回傳「找不到目標」。
4.重複步驟2。
Dijkstra算法
戴克斯特拉算法(Dijkstra’salgorithm)是由荷蘭計算機科學家艾茲赫爾·戴克斯特拉提出。算法使用了廣度優先搜索解決非負權有向圖的單源最短路徑問題,算法最終得到一個最短路徑樹。該算法常用於路由算法或者作為其他圖算法的一個子模塊。
該算法的輸入包含了一個有權重的有向圖G,以及G中的一個來源頂點S。我們以V表示G中所有頂點的集合。每一個圖中的邊,都是兩個頂點所形成的有序元素對。(u,v)表示從頂點u到v有路徑相連。我們以E表示G中所有邊的集合,而邊的權重則由權重函數w:E→[0,∞]定義。因此,w(u,v)就是從頂點u到頂點v的非負權重(weight)。
邊的權重可以想像成兩個頂點之間的距離。任兩點間路徑的權重,就是該路徑上所有邊的權重總和。已知有V中有頂點s及t,Dijkstra算法可以找到s到t的最低權重路徑(例如,最短路徑)。
這個算法也可以在一個圖中,找到從一個頂點s到任何其他頂點的最短路徑。對於不含負權的有向圖,Dijkstra算法是目前已知的最快的單源最短路徑算法。
算法步驟:
1.初始時令S={V0},T={其餘頂點},T中頂點對應的距離值,若存在<V0,Vi>,d(V0,Vi)為<V0,Vi>弧上的權值;若不存在<V0,Vi>,d(V0,Vi)為∞。
2.從T中選取一個其距離值為最小的頂點W且不在S中,加入S。
3.對其餘T中頂點的距離值進行修改:若加進W作中間頂點,從V0到Vi的距離值縮短,則修改此距離值。
重複上述步驟2、3,直到S中包含所有頂點,即W=Vi為止。
動態規划算法
動態規劃(Dynamicprogramming)是一種在數學、計算機科學和經濟學中使用的,通過把原問題分解為相對簡單的子問題的方式求解複雜問題的方法。動態規劃常常適用於有重疊子問題和最優子結構性質的問題,動態規劃方法所耗時間往往遠少於樸素解法。動態規劃背後的基本思想非常簡單。大致上,若要解一個給定問題,我們需要解其不同部分(即子問題),再合併子問題的解以得出原問題的解。
通常許多子問題非常相似,為此動態規劃法試圖僅僅解決每個子問題一次,從而減少計算量:一旦某個給定子問題的解已經算出,則將其記憶化存儲,以便下次需要同一個子問題解之時直接查表。這種做法在重複子問題的數目關於輸入的規模呈指數增長時特別有用。關於動態規劃最經典的問題當屬背包問題。
算法步驟:
1.最優子結構性質。如果問題的最優解所包含的子問題的解也是最優的,我們就稱該問題具有最優子結構性質(即滿足最優化原理)。
最優子結構性質為動態規划算法解決問題提供了重要線索。
2.子問題重疊性質。子問題重疊性質是指在用遞歸算法自頂向下對問題進行求解時,每次產生的子問題並不總是新問題,有些子問題會被重複計算多次。
動態規划算法正是利用了這種子問題的重疊性質,對每一個子問題只計算一次,然後將其計算結果保存在一個表格中,當再次需要計算已經計算過的子問題時,只是在表格中簡單地查看一下結果,從而獲得較高的效率。
樸素貝葉斯分類算法
樸素貝葉斯分類算法是一種基於貝葉斯定理的簡單概率分類算法。貝葉斯分類的基礎是概率推理,就是在各種條件的存在不確定,僅知其出現概率的情況下,如何完成推理和決策任務。
概率推理是與確定性推理相對應的。而樸素貝葉斯分類器是基於獨立假設的,即假設樣本每個特徵與其他特徵都不相關。樸素貝葉斯分類器依靠精確的自然概率模型,在有監督學習的樣本集中能獲取得非常好的分類效果。在許多實際應用中,樸素貝葉斯模型參數估計使用最大似然估計方法,換言之樸素貝葉斯模型能工作並沒有用到貝葉斯概率或者任何貝葉斯模型。儘管是帶著這些樸素思想和過於簡單化的假設,但樸素貝葉斯分類器在很多複雜的現實情形中仍能夠取得相當好的效果。
1、和小浩一起學算法
項目介紹:該項目包括作者小浩撰寫的一本三十萬字的算法題典,以及他收集整理的編程類思維導圖、大廠面經,和不同語言編程電子書等。在這本算法題典中,作者對一些經典算法做了講解。講解的形式是首先給出一道應用該算法的題目,先給出一段文字情境描述,然後給出輸入和輸出的示例。在給出題解之前,作者建議讀者自己思考實現一下,最後,作者還給出了解決原題目的代碼。算法題解這部分適用於計算機科學的初學者閱讀,用題目和圖畫的方式講解算法,易於理解,且能讓初學者印象深刻。讀者藉助編寫代碼實現算法還能做到舉一反三,這是打好算法基礎的關鍵;項目中另一個很吸引人的部分是大廠面試題目匯總。作為拿到大廠 offer 的敲門磚,大廠面試經驗一直受到追捧。但大部分的面試經驗和算法教程一樣,在網絡上零散分布,且不按話題分類。而在本項目中,作者整理了 100 篇面試經驗,並且按照面試題目涉及的知識點進行分類。不僅適合求職者臨陣磨槍,也適合在校生閱讀學習。
項目地址:
https://github.com/geekxh/hello-algorithm
2、算法面試集合
項目介紹:該項目涵蓋2018、2019 的校招/春招/秋招/算法/機器學習(機器學習)/深度學習(深度學習)/自然語言處理(NLP)/ C / C ++ / Python /面試筆記。
項目地址:
https://github.com/yuquanle/Algorithm_Interview_Notes-Chinese
3、Competitive-Programming-Docs
項目介紹:這個項目是一個總資源集,內容非常全面,包含算法競賽論文,課件,文檔,筆記,平臺等資料。
項目地址:
https://github.com/LzyRapx/Competitive-Programming-Docs
4、【算法與數據結構】+一點點ACM從入門到進階吐血整理推薦書單(珍藏版)
項目介紹:該項目收集了關於算法與數據結構的多本電子書。
項目地址:
https://pymlovelyq.github.io/posts/32a7f0eb/
5、負重前行,前端工程師如何系統練習數據結構和算法?【上】
項目介紹:作者詳細提供了系統練習數據結構和算法的方法論。
項目地址:
https://juejin.im/post/6844904061947346957
6、五分鐘學算法:算法與數據結構文章詳細分類與整理!
項目介紹:該項目包含10個數據結構:數組、鍊表、棧、隊列、散列表、二叉樹、堆、跳表、圖、Trie 樹,以及10個算法:遞歸、排序、二分查找、搜索、哈希算法、貪心算法、分治算法、回溯算法、動態規劃、字符串匹配算法。
項目地址:
https://www.cxyxiaowu.com/7072.html
7、算法與面試之-如何準備算法面試
項目介紹:主要介紹算法面試的一些問題、以及如何準備算法面試。
項目地址:
https://juejin.im/post/6844903621105041416
1、LeetCode
估計 leetcode(力扣)大家都很熟悉了,很多國內外的程式設計師在上面刷題,難度從 Easy、Medium 至 Hard 都有,據說很多面試官都會從中挑選各種題目,號稱大廠的篩碼工。
2、LintCode
國外算法練習網站
3、Educative
國外算法練習網站
4、牛客網
牛客網作為國內內容超級豐富的 IT 題庫,各種東西看的我眼花繚亂,題庫+面試+學習+求職+討論 360 度無死角服務,堪稱&34;。它好就好在不只是一個刷題的平臺,還是一個交流學習的平臺。
5、hihoCoder
網站的技術團隊來自於原北大 POJ 的開發團隊,至於 POJ 會在後面的篇章中介紹,反正膜拜就完事了。一些知名的大廠比如微軟、百度、騰訊、網易等會在上面舉辦在線編程比賽,風格倒是和 ACM 比賽類似。
6、HDU
杭電(杭州電子科技大學)的 OJ 大概是國內最火的幾個 OJ 之一了,現在上面大概有接近 6k 的題量,網上有很多的刷題順序,刷題指南。
7、POJ
作為國內最火的幾大 OJ 之一,現在上面有 3k+ 的題量,關於 POJ 的刷題指南網上更是很多。
1、300分鐘搞定數據結構與算法
LeetCode 官方國內唯一合作課程,leetCode刷題秘籍獨家揭秘,專注於面試場景,全程動態動畫教學。
2、數據結構精講:從原理到實戰
Google資深工程師帶你玩轉數據結構,搞懂數據結構底層原理,打敗 97% 的程式設計師。
3、機器學習入門21講
中科院博士帶你輕鬆入門AI。
4、麻省理工學院公開課:算法導論
課程主題包含了:排序、搜尋樹、堆積及散列;各個擊破法、動態規劃、償還分析、圖論算法、最短路徑、網絡流、計算幾何、數字理論性算法;多項式及矩陣的運算;高速緩存技術及並行運算。
5、中國大學MOOC-數據結構
國內關於數據結構非常經典的課程。
1、啊哈!算法(豆瓣評分7.7)
這是一本充滿智慧和趣味的算法入門書。沒有枯燥的描述,沒有難懂的公式,一切以實際應用為出發點,通過幽默的語言配以可愛的插圖來講解算法。你更像是在閱讀一個個輕鬆的小故事或是在玩一把趣味解謎遊戲,在輕鬆愉悅中便掌握算法精髓,感受算法之美。
2、算法圖解(豆瓣評分8.4)
圖文並茂,以讓人容易理解的方式闡釋了算法,旨在幫助程式設計師在日常項目中更好地發揮算法的能量。書中的前三章將幫助你打下基礎,帶你學習二分查找、大O表示法、兩種基本的數據結構以及遞歸等。餘下的篇幅將主要介紹應用廣泛的算法,具體內容包括:面對具體問題時的解決技巧,比如,何時採用貪婪算法或動態規劃;散列表的應用;圖算法;K最近鄰算法。
3、大話數據結構(豆瓣評分7.9)
《大話設計模式》作者程傑潛心三年推出的扛鼎之作,以一個計算機教師教學為場景,講解數據結構和相關算法的知識。通篇以一種趣味方式來敘述,大量引用了各種各樣的生活知識來類比,並充分運用圖形語言來體現抽象內容,對數據結構所涉及到的一些經典算法做到逐行分析、多算法比較。與市場上的同類數據結構圖書相比,本書內容趣味易讀,算法講解細緻深刻,是一本非常適合自學的讀物。
4、算法帝國(豆瓣評分7.2)
本書是《紐約時報》暢銷書作者的又一力作,通過一個又一個引人入勝的故事,向讀者介紹了算法掌控世界的真實情況,揭示了「機器人革命」是如何悄悄地在我們身邊發生的。本書適合任何對科技史、信息革命、算法原理、數據分析感興趣的讀者。
5、算法之美(豆瓣評分7.5)
這本書告訴我們如何更有效地利用直覺、什麼時候應該把選擇權交給命運、無所適從的時候應該如何做出選擇,以及如何有效地與他人保持聯繫。從找配偶到找停車位,從組織管理個人郵箱的收件箱到理解人類記憶的作用原理,這本書把計算機科學的智慧轉化為人類生活的策略,引導我們做出明智的選擇。
6、編程珠璣(豆瓣評分9.1)
本書是計算機科學方面的經典名著。書的內容圍繞程序設計人員面對的一系列實際問題展開。作者Jon Bentley 以其獨有的洞察力和創造力,引導讀者理解這些問題並學會解決方法,而這些正是程式設計師實際編程生涯中至關重要的。本書的特色是通過一些精心設計的有趣而又頗具指導意義的程序,對實用程序設計技巧及基本設計原則進行了透徹而睿智的描述,為複雜的編程問題提供了清晰而完備的解決思路。本書對各個層次的程式設計師都具有很高的閱讀價值。
7、算法謎題(豆瓣評分7.5)
本書可以為對算法感興趣的廣大讀者提供系統豐富而實用的資料,能夠幫助讀者提升高階算法思維能力。本書適合計算機專業的高校教師和學生,想要培養和訓練算法思維和計算思維的IT專業人士,以及在準備面試的應聘者和面試官閱讀參考。
8、算法設計與分析基礎(豆瓣評分8.7)
本書十分適合用作算法設計和分析的基礎教材,也適合任何有興趣探究算法奧秘的讀者使用,只要讀者具備數據結構和離散數學的知識即可。
9、數據結構與算法分析(豆瓣評分8.5)
本書是國外數據結構與算法分析方面的經典教材,使用卓越的Java程式語言作為實現工具討論了數據結構(組織大量數據的方法)和算法分析(對算法運行時間的估計)。隨著計算機速度的不斷增加和功能的日益強大,人們對有效編程和算法分析的要求也不斷增長。本書把算法分析與最有效率的Java程序的開發有機地結合起來,深入分析每種算法,內容全面、縝密嚴格,並細緻講解精心構造程序的方法。
10、算法詳解(卷1)——算法基礎(豆瓣評分8.8)
本書為對算法感興趣的廣大讀者提供了豐富而實用的資料,能夠幫助讀者提升算法思維能力。本書適合計算機專業的高校教師和學生,想要培養和訓練算法思維和計算思維的IT專業人士,以及在準備面試的應聘者和面試官閱讀參考。
11、算法導論(原書第3版)(豆瓣評分9.2)
本書將嚴謹性和全面性融為一體,深入討論各類算法,並著力使這些算法的設計和分析能為各個層次的讀者接受。
12、電腦程式設計藝術(豆瓣評分9.8)
這本書首先介紹編程的基本概念和技術,然後詳細講解信息結構方面的內容,包括信息在計算機內部的表示方法、數據元素之間的結構關係,以及有效的信息處理方法。此外,書中還描述了編程在模擬、數值方法、符號計算、軟體與系統設計等方面的初級應用。此第3版增加了數十項簡單但重要的算法和技術,並根據當前研究發展趨勢在數學預備知識方面做了大量修改。
13、算法第 4 版(豆瓣評分9.3)
《算法(英文版•第4版)》作為算法領域經典的參考書,全面介紹了關於算法和數據結構的必備知識,並特別針對排序、搜索、圖處理和字符串處理進行了論述。第4版具體給出了每位程式設計師應知應會的50個算法,提供了實際代碼,而且這些Java代碼實現採用了模塊化的編程風格,讀者可以方便地加以改造。本書配套網站提供了本書內容的摘要及更多的代碼實現、測試數據、練習、教學課件等資源。
14、算法引論(豆瓣評分9.1)
這本書是國際算法大師烏迪·曼博(Udi Manber)博士撰寫的一本享有盛譽的著作。本書的特色有二,旨在提高讀者的問題求解能力,使讀者能夠理解算法設計的過程和思想:一是強調算法設計的創造性過程,注重算法設計背後的創造性思想,而不拘泥於某個具體算法的詳細討論;二是將算法設計類比於定理歸納證明,揭示了算法設計的基本思想和本質。
15、劍指offer(豆瓣評分8.3)
這本書剖析了50個典型的程式設計師面試題,從基礎知識、代碼質量、解題思路、優化效率和綜合能力五個方面系統整理了影響面試的5個要點。是面試必讀書籍之一。
16、編程之美(豆瓣評分8.4)
這本書收集了約60道算法和程序設計題目,這些題目大部分在近年的筆試、面試中出現過,或者是被微軟員工熱烈討論過。作者試圖從書中各種有趣的問題出發,引導讀者發現問題,分析問題,解決問題,尋找更優的解法。
編輯:於騰凱
校對:林亦霖
——END——
想要獲得更多數據科學領域相關動態,誠邀關注清華-青島數據科學研究院官方微信公眾平臺「 數據派THU 」。