計算機算法是以一步接一步的方式來詳細描述計算機如何將輸入轉化為所要求的輸出的過程，或者說，算法是對計算機上執行的計算過程的具體描述。
基本介紹
算法性質,重要算法,算法特點,算法與程式,
算法性質
一個算法必須具備以下性質：
（1）算法首先必須是正確的，即對於任意的一組輸入，包括合理的輸入與不合理的輸入，總能得到預期的輸出。如果一個算法只是對合理的輸入才能得到預期的輸出，而在異常情況下卻無法預料輸出的結果，那么它就不是正確的。
（2）算法必須是由一系列具體步驟組成的，並且每一步都能夠被計算機所理解和執行，而不是抽象和模糊的概念。
（3）每個步驟都有確定的執行順序，即上一步在哪裡；下一步是什麼，都必須明確，無二義性。
重要算法
A*搜尋算法
俗稱A星算法。這是一種在圖形平面上，有多個節點的路徑，求出最低通過成本的算法。常用於遊戲中的NPC的移動計算，或線上遊戲的BOT的移動計算上。該算法像Dijkstra算法一樣，可以找到一條最短路徑；也像BFS一樣，進行啟發式的搜尋。
Beam Search
束搜尋(beam search)方法是解決最佳化問題的一種啟發式方法，它是在分枝定界方法基礎上發展起來的，它使用啟發式方法估計k個最好的路徑，僅從這k個路徑出發向下搜尋，即每一層只有滿意的結點會被保留，其它的結點則被永久拋棄，從而比分枝定界法能大大節省運行時間。束搜尋於20 世紀70年代中期首先被套用於人工智慧領域,1976 年Lowerre在其稱為HARPY的語音識別系統中第一次使用了束搜尋方法。他的目標是並行地搜尋幾個潛在的最優決策路徑以減少回溯，並快速地獲得一個解。
二分取中查找算法
一種在有序數組中查找某一特定元素的搜尋算法。搜尋過程從數組的中間元素開始，如果中間元素正好是要查找的元素，則搜尋過程結束；如果某一特定元素大於或者小於中間元素，則在數組大於或小於中間元素的那一半中查找，而且跟開始一樣從中間元素開始比較。這種搜尋算法每一次比較都使搜尋範圍縮小一半。
Branch and bound
分支定界(branch and bound)算法是一種在問題的解空間樹上搜尋問題的解的方法。但與回溯算法不同，分支定界算法採用廣度優先或最小耗費優先的方法搜尋解空間樹，並且，在分支定界算法中，每一個活結點只有一次機會成為擴展結點。
數據壓縮
數據壓縮是通過減少計算機中所存儲數據或者通信傳播中數據的冗餘度，達到增大數據密度，最終使數據的存儲空間減少的技術。數據壓縮在檔案存儲和分散式系統領域有著十分廣泛的套用。數據壓縮也代表著尺寸媒介容量的增大和網路頻寬的擴展。
Diffie–Hellman密鑰協商
Diffie–Hellman key exchange，簡稱“D–H”，是一種安全協定。它可以讓雙方在完全沒有對方任何預先信息的條件下通過不安全信道建立起一個密鑰。這個密鑰可以在後續的通訊中作為對稱密鑰來加密通訊內容。
Dijkstra’s 算法
迪科斯徹算法（Dijkstra）是由荷蘭計算機科學家艾茲格·迪科斯徹（Edsger Wybe Dijkstra）發明的。算法解決的是有向圖中單個源點到其他頂點的最短路徑問題。舉例來說，如果圖中的頂點表示城市，而邊上的權重表示著城市間開車行經的距離，迪科斯徹算法可以用來找到兩個城市之間的最短路徑。
動態規劃
動態規劃是一種在數學和計算機科學中使用的，用於求解包含重疊子問題的最最佳化問題的方法。其基本思想是，將原問題分解為相似的子問題，在求解的過程中通過子問題的解求出原問題的解。動態規劃的思想是多種算法的基礎，被廣泛套用於計算機科學和工程領域。比較著名的套用實例有：求解最短路徑問題，背包問題，項目管理，網路流最佳化等。這裡也有一篇文章說得比較詳細。
歐幾里得算法
最大期望（EM）算法
在統計計算中，最大期望（EM）算法是在機率（probabilistic）模型中尋找參數最大似然估計的算法，其中機率模型依賴於無法觀測的隱藏變數（Latent Variable）。最大期望經常用在機器學習和計算機視覺的數據聚類（Data Clustering）領域。最大期望算法經過兩個步驟交替進行計算，第一步是計算期望（E），利用對隱藏變數的現有估計值，計算其最大似然估計值；第二步是最大化（M），最大化在 E 步上求得的最大似然值來計算參數的值。M 步上找到的參數估計值被用於下一個 E 步計算中，這個過程不斷交替進行。
快速傅立葉變換(FFT)
快速傅立葉變換（Fast Fourier Transform，FFT），是離散傅立葉變換的快速算法，也可用於計算離散傅立葉變換的逆變換。快速傅立葉變換有廣泛的套用，如數位訊號處理、計算大整數乘法、求解偏微分方程等等。
哈希函式
HashFunction是一種從任何一種數據中創建小的數字“指紋”的方法。該函式將數據打亂混合，重新創建一個叫做散列值的指紋。散列值通常用來代表一個短的隨機字母和數字組成的字元串。好的散列函式在輸入域中很少出現散列衝突。在散列表和數據處理中，不抑制衝突來區別數據，會使得資料庫記錄更難找到。
堆排序
Heapsort是指利用堆積樹（堆）這種數據結構所設計的一種排序算法。堆積樹是一個近似完全二叉樹的結構，並同時滿足堆積屬性：即子結點的鍵值或索引總是小於（或者大於）它的父結點。
歸併排序
Merge sort是建立在歸併操作上的一種有效的排序算法。該算法是採用分治法（Divide and Conquer）的一個非常典型的套用。
RANSAC 算法
RANSAC 是”RANdom SAmpleConsensus”的縮寫。該算法是用於從一組觀測數據中估計數學模型參數的疊代方法，由Fischler and Bolles在1981提出，它是一種非確定性算法，因為它只能以一定的機率得到合理的結果，隨著疊代次數的增加，這種機率是增加的。該算法的基本假設是觀測數據集中存在”inliers”（那些對模型參數估計起到支持作用的點）和”outliers”（不符合模型的點），並且這組觀測數據受到噪聲影響。RANSAC 假設給定一組”inliers”數據就能夠得到最優的符合這組點的模型。
RSA加密演算法
這是一個公鑰加密算法，也是世界上第一個適合用來做簽名的算法。今天的RSA已經專利失效，其被廣泛地用於電子商務加密，大家都相信，只要密鑰足夠長，這個算法就會是安全的。
並查集Union-find
並查集是一種樹型的數據結構，用於處理一些不相交集合（Disjoint Sets）的合併及查詢問題。常常在使用中以森林來表示。
Viterbi algorithm
尋找最可能的隱藏狀態序列(Finding most probable sequence of hidden states)。
算法特點
1.有窮性。一個算法應包含有限的操作步驟，而不能是無限的。事實上“有窮性”往往指“在合理的範圍之內”。如果讓計算機執行一個歷時1000年才結束的算法，這雖然是有窮的，但超過了合理的限度，人們不把他視為有效算法。
2. 確定性。算法中的每一個步驟都應當是確定的，而不應當是含糊的、模稜兩可的。算法中的每一個步驟應當不致被解釋成不同的含義，而應是十分明確的。也就是說，算法的含義應當是唯一的，而不應當產生“歧義性”。
3. 有零個或多個輸入、所謂輸入是指在執行算法是需要從外界取得必要的信息。
4. 有一個或多個輸出。算法的目的是為了求解，沒有輸出的算法是沒有意義的。
5.有效性。 算法中的每一個 步驟都應當能有效的執行。並得到確定的結果。
算法與程式
雖然算法與電腦程式密切相關，但二者也存在區別：電腦程式是算法的一個實例，是將算法通過某種計算機語言表達出來的具體形式；同一個算法可以用任何一種計算機語言來表達。
算法列表
圖論
路徑問題
0/1邊權最短路徑
BFS
非負邊權最短路徑（Dijkstra）
可以用Dijkstra解決問題的特徵
負邊權最短路徑
Bellman-Ford
Bellman-Ford的Yen-氏最佳化
Floyd
廣義路徑問題
傳遞閉包
極小極大距離 / 極大極小距離
Euler Path / Tour
圈套圈算法
混合圖的 Euler Path / Tour
Hamilton Path / Tour
特殊圖的Hamilton Path / Tour 構造
生成樹問題
第k小生成樹
最優比率生成樹
0/1分數規劃
度限制生成樹
連通性問題
強大的DFS算法
無向圖連通性
割點
割邊
二連通分支
有向圖連通性
強連通分支
2-SAT
最小點基
有向無環圖
拓撲排序
有向無環圖與動態規劃的關係
二分圖匹配問題
一般圖問題與二分圖問題的轉換思路
最大匹配
有向圖的最小路徑覆蓋
0 / 1矩陣的最小覆蓋
完備匹配
穩定婚姻
網路流問題
網路流模型的簡單特徵和與線性規劃的關係
最大流最小割定理
最大流問題
有上下界的最大流問題
循環流
最小費用最大流 / 最大費用最大流
弦圖的性質和判定
解決組合數學問題時常用的思想
逼近
機率問題
Polya定理
計算幾何 / 解析幾何
計算幾何的核心：叉積 / 面積
解析幾何的主力：複數
基本形
點
直線，線段
多邊形
凸多邊形 / 凸包
凸包算法的引進，卷包裹法
Graham掃描法
水平序的引進，共線凸包的補丁
完美凸包算法
相關判定
兩直線相交
兩線段相交
點在任意多邊形內的判定
點在凸多邊形內的判定
經典問題
最小外接圓
近似O(n)的最小外接圓算法
點集直徑
旋轉卡殼，對踵點
多邊形的三角剖分
數學/數論
擴展的Euclid算法
同餘方程 / 二元一次不定方程
同餘方程組
線性方程組
解mod 2域上的線性方程組
整係數方程組的精確解法
行列式的計算
分數
分數樹
連分數逼近
數論計算
求N的約數個數
求phi(N)
求約數和
快速數論變換
……
素數問題
機率判素算法
機率因子分解
數據結構
