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

Metropolis算法

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

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

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

為啥這個算法牛？Metropolis算法是蒙特卡洛方法中最著名的算法，它的應(yīng)用領(lǐng)域包括統(tǒng)計物理、QCD、天體物理、物理化學(xué)、數(shù)學(xué)、計算生物、人工智能等等，甚至是社會科學(xué)。

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

單純形法

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

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

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

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

快速傅立葉算法

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

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

再增加一個速率圓周運

再增加幾個看看：

是不是已經(jīng)很接近方波了？

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

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

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

James Cooley：

John Tukey：

計算量小的顯著的優(yōu)點，使得FFT在信號處理技術(shù)領(lǐng)域獲得了廣泛應(yīng)用，結(jié)合高速硬件就能實現(xiàn)對信號的實時處理。例如，對語音信號的分析和合成，對通信系統(tǒng)中實現(xiàn)全數(shù)字化的時分制與頻分制(TDM/FDM)的復(fù)用轉(zhuǎn)換，在頻域?qū)π盘枮V波以及相關(guān)分析，通過對雷達、聲納、振動信號的頻譜分析以提高對目標(biāo)的搜索和跟蹤的分辨率等等，都要用到FFT?？梢哉fFFT的出現(xiàn)，對數(shù)字信號處理學(xué)科的發(fā)展起了重要的作用。

快速排序算法

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

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

計算特征值的QR算法

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

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

系統(tǒng)辨識是現(xiàn)代控制理論的重要組成部分。對系統(tǒng)的結(jié)構(gòu)和參數(shù)進行辨識在工程上和理論上都占有重要的地位。最小二乘法是系統(tǒng)參數(shù)辨識中的重要估計方法,并在眾多領(lǐng)域和場合得到了廣泛的應(yīng)用。

QR分解算法在現(xiàn)在火熱的人工智能領(lǐng)域更是基礎(chǔ)算法之一，有此有其是改變世界的算法并不夸張。