導(dǎo)語：

在程序員圈子里，經(jīng)常討論哪家大廠的算法如何厲害。那么，算法這個讓程序員情感復(fù)雜的東西，到底“厲害”在何處？算法對于程序員是否重要？作為一個合格的程序員，應(yīng)該掌握哪些算法？本期，就和大家一起探索，“算法到底是什么”。

應(yīng)對燈泡不亮的算法流程圖

算法的前世今生

算法（algorithm）作為在數(shù)學(xué)（算學(xué)）和計算機科學(xué)之中的一個有效方法，是一個被定義好的、計算機可施行指示的有限步驟或次序，常用于計算、數(shù)據(jù)處理和自動推理。它包含了一系列定義清晰的指令，并可于有限的時間及空間內(nèi)清楚的表述出來。

用通俗的方式來理解，可以把算法比作食譜。讓對烘焙一無所知的人，也可以根據(jù)食譜上所提供的“算法”步驟，按比例混合材料，用適當?shù)暮兔媪Χ龋刂瓶局茣r間，做出美味的面包。

同時，每一次烤制面包，都不需要重新研究烘焙的方法。這也是“算法”的初步特征：算法是解決問題的手段。我們不需要為每個同類問題，都發(fā)明一個解決方案。因此，算法是一勞永逸式的工作方法。

離開如今狹義的互聯(lián)網(wǎng)術(shù)語，在千年之前，人們關(guān)于算法的探索就已經(jīng)開始，在中國古代，算法被稱為“術(shù)”。最早出現(xiàn)在《周髀算經(jīng)》、《九章算術(shù)》。特別是《九章算術(shù)》，給出四則運算、最大公約數(shù)、最小公倍數(shù)、開平方根、開立方根、求素數(shù)的埃拉托斯特尼篩法，線性方程組求解的算法。

西方世界，大約公元前300年，歐幾里得算法出現(xiàn)，被人們認為是史上第一個算法。時間來到1842年，愛達·勒芙蕾絲為“巴貝奇分析機”編寫求解“解伯努利微分方程”的程序，因此愛達·勒芙蕾絲被大多數(shù)人認為是世界上第一位程序員。緊接著，20世紀的英國數(shù)學(xué)家圖靈提出了著名的圖靈論題，并提出一種假想的計算機的抽象模型，這個模型被稱為圖靈機。

也是從圖靈機開始，算法真正在計算機領(lǐng)域開始應(yīng)用。對于算法的“前世”有所了解，那么“今生”的算法對于程序員究竟有多重要呢？

從廣義來講，算法從數(shù)學(xué)、邏輯學(xué)，甚至是編程哲學(xué)的角度，對每個學(xué)習(xí)者及應(yīng)用者產(chǎn)生影響。它雖然不是學(xué)來就用的東西，但對于程序員，重要到?jīng)Q定了他們可以在這個行業(yè)里走多遠的程度。

對于程序員，算法是方法、思想，是一種解決問題的思維方式。就像是食譜，它鍛煉你遇到有序的問題時，以計算機的“思維方式”，利用規(guī)律的特性來解決問題。在不斷優(yōu)化程序員的編程思維。在未來的工作中，也許程序員不會用到形式上的算法，但這種底層方法論已融入到程序員的工作思維里面。

在實際工作中，需要去閱讀一些代碼的時候，也確實需要算法功底，例如在看leveldb、redis源代碼時，需要知道跳表是什么意思；看Linux vma要知道紅黑樹是什么；看page cache要懂得基數(shù)樹。

最后，無論程序員多么抗拒算法，但也要有所學(xué)習(xí)來應(yīng)對面試。

在程序員面試中，有75%的題目都會與算法、數(shù)據(jù)結(jié)構(gòu)相關(guān)，尤其是國外的一些公司，算法是面試中考察的重中之重，尤其是國外管理者特別喜歡那些ACM競賽經(jīng)驗的面試者。面試時，當面試官忽然一句“關(guān)于算法，你……”的問題拋來，面試者無法應(yīng)對，可能便直接涼涼回家。

10個程序員要知道的算法

在程序員的日常工作中，有以下十個程序員要知道的基礎(chǔ)算法。

1.快速排序算法

快速排序是由東尼·霍爾所提出的一種排序算法。在平均狀況下，排序n個項目要Ο(nlogn)次比較。在最壞狀況下則需要Ο(n2)次比較，但這種狀況并不常見?？焖倥判蛲ǔＣ黠@比其他Ο(nlogn)算法更快，因為它的內(nèi)部循環(huán)（innerloop）可以在大部分的架構(gòu)上很有效率地被實現(xiàn)出來。

2.堆排序算法

堆排序（Heapsort）是指利用堆這種數(shù)據(jù)結(jié)構(gòu)所設(shè)計的一種排序算法。堆積是一個近似完全二叉樹的結(jié)構(gòu)，并同時滿足堆積的性質(zhì)：即子結(jié)點的鍵值或索引總是小于（或者大于）它的父節(jié)點。堆排序的平均時間復(fù)雜度為Ο(nlogn) 。

3.歸并排序

歸并排序（Mergesort）是建立在歸并操作上的一種有效的排序算法。該算法是采用分治法（DivideandConquer）的一個非常典型的應(yīng)用。

4.二分查找算法

二分查找算法是一種在有序數(shù)組中查找某一特定元素的搜索算法。

搜素過程從數(shù)組的中間元素開始，如果中間元素正好是要查找的元素，則搜素過程結(jié)束，如果某一特定元素大于或小于中間元素，則在數(shù)組大于或小于中間元素的那一半中查找，而且跟開始一樣從中間元素開始比較。

如果在某一步驟數(shù)組為空，則代表找不到。這種搜索算法每一次比較都使搜索范圍縮小一半。折半搜索每次把搜索區(qū)域減少一半，時間復(fù)雜度為Ο(logn) 。

5.BFPRT(線性查找算法)

BFPRT算法解決的問題十分經(jīng)典，即從某n個元素的序列中選出第k大（第k?。┑脑?，通過巧妙的分析，BFPRT可以保證在最壞情況下仍為線性時間復(fù)雜度。

該算法的思想與快速排序思想相似，當然，為使得算法在最壞情況下，依然能達到O(n)的時間復(fù)雜度，五位算法作者做了精妙的處理。

6.DFS（深度優(yōu)先搜索）

深度優(yōu)先搜索算法（Depth-First-Search），是搜索算法的一種。

它沿著樹的深度遍歷樹的節(jié)點，盡可能深的搜索樹的分支。當節(jié)點v的所有邊都己被探尋過，搜索將回溯到發(fā)現(xiàn)節(jié)點v的那條邊的起始節(jié)點。

這一過程一直進行到已發(fā)現(xiàn)從源節(jié)點可達的所有節(jié)點為止。如果還存在未被發(fā)現(xiàn)的節(jié)點，則選擇其中一個作為源節(jié)點并重復(fù)以上過程，整個進程反復(fù)進行直到所有節(jié)點都被訪問為止。

7.BFS(廣度優(yōu)先搜索)

廣度優(yōu)先搜索算法（Breadth-First-Search），是一種圖形搜索算法。簡單的說，BFS是從根節(jié)點開始，沿著樹(圖)的寬度遍歷樹(圖)的節(jié)點。

如果所有節(jié)點均被訪問，則算法中止。BFS同樣屬于盲目搜索。一般用隊列數(shù)據(jù)結(jié)構(gòu)來輔助實現(xiàn)BFS算法。

8.Dijkstra算法

戴克斯特拉算法（Dijkstra’salgorithm）是由荷蘭計算機科學(xué)家艾茲赫爾·戴克斯特拉提出。

迪科斯徹算法使用了廣度優(yōu)先搜索解決非負權(quán)有向圖的單源最短路徑問題，算法最終得到一個最短路徑樹。該算法常用于路由算法或者作為其他圖算法的一個子模塊。

該算法的輸入包含了一個有權(quán)重的有向圖G，以及G中的一個來源頂點S。以V表示G中所有頂點的集合。

每一個圖中的邊，都是兩個頂點所形成的有序元素對。(u,v)表示從頂點u到v有路徑相連。我們以E表示G中所有邊的集合，而邊的權(quán)重則由權(quán)重函數(shù)w:E→[0,∞]定義。因此，w(u,v)就是從頂點u到頂點v的非負權(quán)重（weight）。

邊的權(quán)重可以想像成兩個頂點之間的距離。任兩點間路徑的權(quán)重，就是該路徑上所有邊的權(quán)重總和。已知有V中有頂點s及t，Dijkstra算法可以找到s到t的最低權(quán)重路徑(例如，最短路徑)。

這個算法也可以在一個圖中，找到從一個頂點s到任何其他頂點的最短路徑。對于不含負權(quán)的有向圖，Dijkstra算法是目前已知的最快的單源最短路徑算法。

9.動態(tài)規(guī)劃算法

動態(tài)規(guī)劃（Dynamicprogramming）是一種在數(shù)學(xué)、計算機科學(xué)和經(jīng)濟學(xué)中使用的，通過把原問題分解為相對簡單的子問題的方式求解復(fù)雜問題的方法。

動態(tài)規(guī)劃常常適用于有重疊子問題和最優(yōu)子結(jié)構(gòu)性質(zhì)的問題，動態(tài)規(guī)劃方法所耗時間往往遠少于樸素解法。

動態(tài)規(guī)劃背后的基本思想非常簡單。大致上，若要解一個給定問題，我們需要解其不同部分（即子問題），再合并子問題的解以得出原問題的解。

通常許多子問題非常相似，為此動態(tài)規(guī)劃法試圖僅僅解決每個子問題一次，從而減少計算量：一旦某個給定子問題的解已經(jīng)算出，則將其記憶化存儲，以便下次需要同一個子問題解之時直接查表。這種做法在重復(fù)子問題的數(shù)目關(guān)于輸入的規(guī)模呈指數(shù)增長時特別有用。

關(guān)于動態(tài)規(guī)劃最經(jīng)典的問題當屬背包問題。

10.樸素貝葉斯分類算法

樸素貝葉斯分類算法是一種基于貝葉斯定理的簡單概率分類算法。貝葉斯分類的基礎(chǔ)是概率推理，就是在各種條件的存在不確定，僅知其出現(xiàn)概率的情況下，如何完成推理和決策任務(wù)。

概率推理是與確定性推理相對應(yīng)的，而樸素貝葉斯分類器是基于獨立假設(shè)的，即假設(shè)樣本每個特征與其他特征都不相關(guān)。

樸素貝葉斯分類器依靠精確的自然概率模型，在有監(jiān)督學(xué)習(xí)的樣本集中能獲取得非常好的分類效果。在許多實際應(yīng)用中，樸素貝葉斯模型參數(shù)估計使用最大似然估計方法，換言之樸素貝葉斯模型能工作并沒有用到貝葉斯概率或者任何貝葉斯模型。

盡管是帶著這些樸素思想和過于簡單化的假設(shè)，但樸素貝葉斯分類器在很多復(fù)雜的現(xiàn)實情形中仍能夠取得相當好的效果。

了解到算法的重要性，是否有興趣加強一下算法學(xué)習(xí)呢？但別著急，算法從誕生到如今為人們應(yīng)用，走過了千年時光。我們從學(xué)習(xí)到得心應(yīng)手，也不是一朝一夕便能做到。

最后還有句話是這么說的：栽一棵樹最好的時間是十年前，其次是現(xiàn)在。對于學(xué)習(xí)編程或者在工作想升職的程序員，如果你想更好的提升你的編程核心能力（內(nèi)功），在面試時有充分的準備和自信！筆者這里或許可以幫到你~

微信公眾號：C語言編程學(xué)習(xí)基地

分享（源碼、項目實戰(zhàn)視頻、項目筆記，基礎(chǔ)入門教程）

歡迎轉(zhuǎn)行和學(xué)習(xí)編程的伙伴，利用更多的資料學(xué)習(xí)成長比自己琢磨更快哦！