優秀程式設計師該學的32個演算法！！

1、A搜尋演算法——圖形搜尋演算法，作為啟發式搜尋演算法中的一種，這是一種在圖形平面上，有多個節點的路徑，求出最低透過成本的演算法，常用於遊戲中的NPC的移動計算，或線上遊戲的BOT的移動計算上。

從給定起點到給定終點計算出路徑。其中使用了一種啟發式的估算，為每個節點估算透過該節點的最佳路徑，並以之為各個地點排定次序。演算法以得到的次序訪問這些節點。因此，A*搜尋演算法是最佳優先搜尋的範例。

2、集束搜尋（又名定向搜尋，Beam Search）——最佳優先搜尋演算法的最佳化。使用啟發式函式評估它檢查的每個節點的能力。不過，集束搜尋只能在每個深度中發現最前面的m個最符合條件的節點，m是固定數字——集束的寬度。

通常用在圖的解空間比較大的情況下，為了減少搜尋所佔用的空間和時間，在每一步深度擴充套件的時候，剪掉一些質量比較差的結點，保留下一些質量較高的結點。這樣減少了空間消耗，並提高了時間效率

演算法的工作流程如下：

使用廣度優先策略建立搜尋樹，在樹的每一層，按照啟發代價對節點進行排序，然後僅留下預先確定的個數（Beam Width-集束寬度）的節點，僅這些節點在下一層次繼續擴充套件，其他節點就被剪掉了。

將初始節點插入到list中，

將給節點出堆，如果該節點是目標節點，則演算法結束；

否則擴充套件該節點，取集束寬度的節點入堆。然後到第二步繼續迴圈。

演算法結束的條件是找到最優解或者堆為空。

3、二分查詢（Binary Search）——線上性陣列中找特定值的演算法，每個步驟去掉一半不符合要求的資料。

二分查詢的基本思想是：

設R[low..high]是當前的查詢區間

（1）首先確定該區間的中點位置：

（2）然後將待查的K值與R[mid].key比較：若相等，則查詢成功並返回此位置，否則須確定新的查詢區間，繼續二分查詢，具體方法如下：

① 若R[mid].key>K，則由表的有序性可知R[mid..n].keys均大於K，因此若表中存在關鍵字等於K的結點，則該結點必定是在位置mid左邊的子表R[1..mid-1]中，故新的查詢區間是左子表R[1..mid-1]。

② 若R[mid].key<K，則要查詢的K必在mid的右子表R[mid+1..n]中，即新的查詢區間是右子表R[mid+1..n]。下一次查詢是針對新的查詢區間進行的。

4、分支界定演算法（Branch and Bound）——在多種最最佳化問題中尋找特定最最佳化解決方案的演算法，特別是針對離散、組合的最最佳化。

搜尋策略是：

B在產生的孩子節點中，剪掉那些不可能產生可行解（或最優解）的節點；（使用限定條件）

C將其餘所有的孩子節點加入活節點連結串列；

D從活結點表中選擇下一個活結點作為新的擴充套件節點；

E遇到層結束標記（採取不同的資料結構實現可能不同， 加入新的結束標記）

如此迴圈，直到找到問題的可行解（或最優解）或者活結點表為空。

分支界定法的思想是：首先確定目標值的上下界， 邊搜尋邊減掉搜尋樹的某些枝， 提高搜尋效率。

5、Buchberger演算法——一種數學演算法，可將其視為針對單變數最大公約數求解的歐幾里得演算法和線性系統中高斯消元法的泛化。

7、Diffie-Hellman金鑰交換演算法——一種加密協議，允許雙方在事先不瞭解對方的情況下，在不安全的通訊通道中，共同建立共享金鑰。該金鑰以後可與一個對稱密碼一起，加密後續通訊。

8、Dijkstra演算法——針對沒有負值權重邊的有向圖，計算其中的單一起點最短演算法。

9、離散微分演算法（Discrete differentiation）

10、動態規劃演算法（Dynamic Programming）——展示互相覆蓋的子問題和最優子架構演算法

11、歐幾里得演算法（Euclidean algorithm）——計算兩個整數的最大公約數。最古老的演算法之一，出現在公元前300前歐幾里得的《幾何原本》。

12、期望-最大演算法（Expectation-maximization algorithm，又名EM-Training）——在統計計算中，期望-最大演算法在機率模型中尋找可能性最大的引數估算值，其中模型依賴於未發現的潛在變數。EM在兩個步驟中交替計算，第一步是計算期望，利用對隱藏變數的現有估計值，計算其最大可能估計值；第二步是最大化，最大化在第一步上求得的最大可能值來計算引數的值。

13、快速傅立葉變換（Fast Fourier transform，FFT）——計算離散的傅立葉變換（DFT）及其反轉。該演算法應用範圍很廣，從數字訊號處理到解決偏微分方程，到快速計算大整數乘積。

14、梯度下降（Gradient descent）——一種數學上的最最佳化演算法。

15、雜湊演算法（Hashing）

Hash演算法是一種只能加密不能解密的演算法，可以將任意長度的資訊轉成雜亂的固定長度的字串，叫做Hash值，又稱“訊息摘要”（Message Digest)也可以說，hash就是找到一種資料內容和資料存放地址之間的對映關係。由於非對稱演算法的運算速度較慢，所以在數字簽名協議中，雜湊函式扮演了一個重要的角色而被用於數字簽名。

雜湊演算法具有以下2個特點：

1.輸入值只要改變一點，輸出的hash值會天差地別。因此只有完全一樣的輸入值才能達到完全一樣的輸出值2.輸入值和輸出值之間沒有規律，所以不能透過輸出值反推出輸入值。

16、堆排序（Heaps）

指利用堆積樹（堆）這種資料結構所設計的一種排序演算法，它是選擇排序的一種。可以利用陣列的特點快速定位指定索引的元素。堆分為大根堆和小根堆，是完全二叉樹。

17、Karatsuba乘法——需要完成上千位整數的乘法的系統中使用，比如計算機代數系統和大數程式庫，如果使用長乘法，速度太慢。該演算法發現於1962年。

18、LLL演算法（Lenstra-Lenstra-Lovasz lattice reduction）——以格規約（lattice）基數為輸入，輸出短正交向量基數。LLL演算法在以下公共金鑰加密方法中有大量使用：揹包加密系統（knapsack）、有特定設定的RSA加密等等。

19、最大流量演算法（Maximum flow）——該演算法試圖從一個流量網路中找到最大的流。它優勢被定義為找到這樣一個流的值。最大流問題可以看作更復雜的網路流問題的特定情況。最大流與網路中的介面有關，這就是最大流-最小截定理（Max-flow min-cut theorem）。Ford-Fulkerson 能找到一個流網路中的最大流。

20、合併排序（Merge Sort）

具體步驟如下：

將待排序的陣列分成左右兩部分。再將這兩部分分別分成左右兩部分。一直分下去，直到不可分（每部分只有一個元素）。由於陣列被分成許多的單個數據，比較起來就簡單了，然後開始合併，合併的同時排序。持續合併直到得到排好序的陣列。

下面這幅圖可以幫助你理解演算法過程：

21、牛頓法（Newton"s method）——求非線性方程（組）零點的一種重要的迭代法。

同梯度下降法一樣，是一種最佳化演算法，其應用如可解決logistic迴歸於分類問題中的似然函式最大化。

其是一種用於求函式零點的數值方法。

22、Q-learning學習演算法——這是一種透過學習動作值函式（action-value function）完成的強化學習演算法，函式採取在給定狀態的給定動作，並計算出期望的效用價值，在此後遵循固定的策略。Q-leanring的優勢是，在不需要環境模型的情況下，可以對比可採納行動的期望效用。

23、兩次篩法（Quadratic Sieve）——現代整數因子分解演算法，在實踐中，是目前已知第二快的此類演算法（僅次於數域篩法Number Field Sieve）。對於110位以下的十位整數，它仍是最快的，而且都認為它比數域篩法更簡單。

24、RANSAC——是“RANdom SAmple Consensus”的縮寫。該演算法根據一系列觀察得到的資料，資料中包含異常值，估算一個數學模型的引數值。其基本假設是：資料包含非異化值，也就是能夠透過某些模型引數解釋的值，異化值就是那些不符合模型的資料點。

25、RSA——公鑰加密演算法。首個適用於以簽名作為加密的演算法。RSA在電商行業中仍大規模使用，大家也相信它有足夠安全長度的公鑰。

26、Schönhage-Strassen演算法——在數學中，Schönhage-Strassen演算法是用來完成大整數的乘法的快速漸近演算法。其演算法複雜度為：O(N log(N) log(log(N)))，該演算法使用了傅立葉變換。

27、單純型演算法（Simplex Algorithm）——在數學的最佳化理論中，單純型演算法是常用的技術，用來找到線性規劃問題的數值解。線性規劃問題包括在一組實變數上的一系列線性不等式組，以及一個等待最大化（或最小化）的固定線性函式。

28、奇異值分解（Singular value decomposition，簡稱SVD）——線上性代數中，SVD是重要的實數或複數矩陣的分解方法，在訊號處理和統計中有多種應用，比如計算矩陣的偽逆矩陣（以求解最小二乘法問題）、解決超定線性系統（overdetermined linear systems）、矩陣逼近、數值天氣預報等等。

29、求解線性方程組（Solving a system of linear equations）——線性方程組是數學中最古老的問題，它們有很多應用，比如在數字訊號處理、線性規劃中的估算和預測、數值分析中的非線性問題逼近等等。求解線性方程組，可以使用高斯—約當消去法（Gauss-Jordan elimination），或是柯列斯基分解（ Cholesky decomposition）。

Strukturtensor演算法——應用於模式識別領域，為所有畫素找出一種計算方法，看看該畫素是否處於同質區域（ homogenous region），看看它是否屬於邊緣，還是是一個頂點。

30、合併查詢演算法（Union-find）——給定一組元素，該演算法常常用來把這些元素分為多個分離的、彼此不重合的組。不相交集（disjoint-set）的資料結構可以跟蹤這樣的切分方法。合併查詢演算法可以在此種資料結構上完成兩個有用的操作：

I、查詢：判斷某特定元素屬於哪個組。

II、合併：聯合或合併兩個組為一個組。

31、維特比演算法（Viterbi algorithm）——尋找隱藏狀態最有可能序列的動態規劃演算法，這種序列被稱為維特比路徑，其結果是一系列可以觀察到的事件，特別是在隱藏的Markov模型中。

32、維特比演算法（Viterbi algorithm）——尋找隱藏狀態最有可能序列的動態規劃演算法，這種序列被稱為維特比路徑，其結果是一系列可以觀察到的事件，特別是在隱藏的Markov模型中。