[導讀] 算法（Algorithm）是指解題方案的準確而完整的描述，是一系列解決問題的清晰指令，算法代表著用系統的方法描述解決問題的策略機制。周末了，今天來輕松概念性總結分享一下改變世界5大算法，當然足以改變世界的算法遠不止這5個。比如還有卡爾曼濾波算法啦等等，等以后有機會整理。

Metropolis算法

在統計和統計物理學中，Metropolis-Hastings算法是一種馬爾可夫鏈蒙特卡洛（MCMC）方法，用于從難以直接采樣的概率分布中獲取隨機樣本序列。該序列可用于近似分布（例如，生成直方圖）或計算積分（例如，期望值）。Metropolis-Hastings和其他MCMC算法通常用于多維分布的采樣，尤其是在維數較多時。對于一維分布，通常還有其他方法（例如自適應拒絕采樣）可以直接從分布中返回獨立樣本，并且這些方法不會出現MCMC方法固有的自相關樣本問題。

Metropolis算法是一種根據Boltzmann分布生成系統狀態的Markov-Chain-Monte-Carlo方法。從該算法中衍生出的更通用的Metropolis-Hastings算法可以模擬隨機變量序列，更精確地模擬了期望分布為平穩分布的馬爾科夫鏈，特別是在許多隨機變量的分布無法直接模擬的情況下。

該算法以Nicholas Metropolis的名字命名，后者與Arianna W. Rosenbluth，Marshall Rosenbluth，Augusta H. Teller和Edward Teller共同撰寫了1953年的文章《Equation of State Calculations by Fast Computing Machines》。

為啥這個算法牛？Metropolis算法是蒙特卡洛方法中最著名的算法，它的應用領域包括統計物理、QCD、天體物理、物理化學、數學、計算生物、人工智能等等，甚至是社會科學。

使用Metropolis-Hastings算法在Rosenbrock函數上運行的3D馬爾可夫鏈的結果。該算法從后驗概率高的區域采樣，鏈開始在這些區域混合。

單純形法

在數學優化中，Dantzig的單純形算法（或單純形方法）是用于線性規劃的一種流行算法。該算法的名稱源自單純形的概念，由T. S. Motzkin提出。單純形法（也稱為單純形算法）是用于解決線性優化問題的數值優化方法，也稱為線性程序（LP）。它僅需經過有限的多個步驟即可解決此問題，或者確定其不溶性或無限性。單純形法的基本思想是1947年由George Dantzig提出的。從那以后，通過大量改進，它們已發展成為實際中最重要的線性優化解決方案。單純形法是樞軸法

一個線性不等式系統將一個多面體定義為一個可行域。單純形算法從一個起始點開始，沿著多面體的邊緣移動，直到到達最優解的頂點。

3D中的單純形算法多面體：

如今線性規劃的理論與算法均非常成熟，在實際問題和生產生活中的應用非常廣泛；線性規劃問題的誕生標志著一個新的應用數學分支———數學規劃時代的到來。過去的 60 年中，數學規劃已經成為一門成熟的學科。其理論與方法被應用到經濟、 金融、 軍事、機器學習等各個領域。數學規劃領域內，其他重要分支的很多問題是在線性規劃理論與算法的基礎上建立起來的， 同時也是利用線性規劃的理論來解決和處理的。由此可見， 線性規劃問題在整個數學規劃和應用數學領域中占有重要地位。因此， 研究單純形法的產生與發展對于認識整個數學規劃的發展有重大意義

快速傅立葉算法

啥是傅立葉變換？表示能將滿足一定條件的某個函數表示成三角函數（正弦和/或余弦函數）或者它們的積分的線性組合。在不同的研究領域，傅立葉變換具有多種不同的變體形式，如連續傅立葉變換和離散傅立葉變換。最初傅立葉分析是作為熱過程的解析分析的工具被提出的。通過下面幾步看一下近似方波近似疊加過程：

如果一個點以恒定的速度繞圓周運動，那么它離地面的高度就是一個正弦函數。點移動的速度對應于頻率，圓的半徑對應于振幅。

再增加一個速率圓周運

再增加幾個看看：

是不是已經很接近方波了？

而快速傅立葉變換（FFT）是用于高效計算離散傅立葉變換（DFT）的算法。它可以用于將數字信號分解為頻率分量，然后可以對其進行分析。類似地，存在離散傅里葉逆快速傅里葉逆變換（IFFT）。IFFT使用相同的算法，但具有共軛系數。

下圖展示一個時域信號做FFT后的譜線圖：

快速傅里葉變換是1965年由J.W.庫利和T.W.圖基提出的。采用這種算法能使計算機計算離散傅里葉變換所需要的乘法次數大為減少，特別是被變換的抽樣點數N越多，FFT算法計算量的節省就越顯著。

James Cooley：

John Tukey：

計算量小的顯著的優點，使得FFT在信號處理技術領域獲得了廣泛應用，結合高速硬件就能實現對信號的實時處理。例如，對語音信號的分析和合成，對通信系統中實現全數字化的時分制與頻分制(TDM/FDM)的復用轉換，在頻域對信號濾波以及相關分析，通過對雷達、聲納、振動信號的頻譜分析以提高對目標的搜索和跟蹤的分辨率等等，都要用到FFT?？梢哉fFFT的出現，對數字信號處理學科的發展起了重要的作用。

快速排序算法

大家熟知的快速排序是一種快速的、遞歸的、非穩定的排序算法，它的工作原理是部分和優勢。它是在1960年左右由C.安東尼R.霍爾(C. Antony R. Hoare)開發出來的基本形式，后來經過許多研究人員的改進。該算法的優點是有一個非常短的內部循環(這大大提高了執行速度)。它不需要額外的內存(除了遞歸調用堆棧上需要的額外空間之外)。

這算法應用在計算機科學中大量應用自不必多說。當然也是本文幾個算法相對容易理解的算法。這算法對現代軟件編程影響深遠，大浪淘沙，流傳久遠！

計算特征值的QR算法

QR算法是一種計算所有特征值和二次矩陣特征向量的數值方法。QR法或QR迭代法是在QR分解的基礎上，由John G. F. Francis和Wera Nikolajewna Kublanowskaja在1961-1962年獨立提出的。其前身是Heinz Rutishauser(1958)提出的LR算法，該算法穩定性較差，基于LR分解。QR算法的迭代往往收斂于矩陣的Schur形式。最初的過程相當復雜，因此，即使在今天的計算機上，對于具有數十萬行和列的矩陣也是不可行的。

派生的變體，如Z. Bai和James Demmel 1989的多移位方法和K. Braman、R. Byers和R. Mathias 2002的在數值上更穩定的變體，具有實際運行時，其大小為矩陣的立方。后一種方法在數值軟件庫LAPACK中實現，而后者在許多計算機代數系統(CAS)中用于數值矩陣算法

系統辨識是現代控制理論的重要組成部分。對系統的結構和參數進行辨識在工程上和理論上都占有重要的地位。最小二乘法是系統參數辨識中的重要估計方法,并在眾多領域和場合得到了廣泛的應用。

QR分解算法在現在火熱的人工智能領域更是基礎算法之一，有此有其是改變世界的算法并不夸張。