第一篇：20世紀(jì)10大算法(數(shù)學(xué)、電子信息、計(jì)算機(jī)等專(zhuān)業(yè)必備基本背景知識(shí))

本世紀(jì)初，美國(guó)物理學(xué)會(huì)(American Institute of Physics)和IEEE計(jì)算機(jī)社團(tuán)(IEEE Computer Society)的一本聯(lián)合刊物《科學(xué)與工程中的計(jì)算》發(fā)表了由田納西大學(xué)的Jack Dongarra和橡樹(shù)嶺國(guó)家實(shí)驗(yàn)室的Francis Sullivan 聯(lián)名撰寫(xiě)的“世紀(jì)十大算法”一文，該文“試圖整理出在20世紀(jì)對(duì)科學(xué)和工程領(lǐng)域的發(fā)展產(chǎn)生最大影響力的十大算法”。作者苦于“任何選擇都將是充滿(mǎn)爭(zhēng)議的，因?yàn)閷?shí)在是沒(méi)有最好的算法”，他們只好用編年順序依次列出了這十項(xiàng)算法領(lǐng)域人類(lèi)智慧的巔峰之作——給出了一份沒(méi)有排名的算法排行榜。有趣的是，該期雜志還專(zhuān)門(mén)邀請(qǐng)了這些算法相關(guān)領(lǐng)域的“大拿”為這十大算法撰寫(xiě)十篇綜述文章，實(shí)在是蔚為壯觀。本文的目的，便是要帶領(lǐng)讀者走馬觀花，一同回顧當(dāng)年這一算法界的盛舉。

1946 蒙特卡洛方法

在廣場(chǎng)上畫(huà)一個(gè)邊長(zhǎng)一米的正方形，在正方形內(nèi)部隨意用粉筆畫(huà)一個(gè)不規(guī)則的形狀，呃，能幫我算算這個(gè)不規(guī)則圖形的面積么？蒙特卡洛(Monte Carlo)方法便是解決這個(gè)問(wèn)題的巧妙方法:隨機(jī)向該正方形內(nèi)扔N（N 是一個(gè)很大的自然數(shù)）個(gè)黃豆，隨后數(shù)數(shù)有多少個(gè)黃豆在這個(gè)不規(guī)則幾何形狀內(nèi)部，比如說(shuō)有M個(gè):那么，這個(gè)奇怪形狀的面積便近似于M/N，N越大，算出來(lái)的值便越精確。別小看這個(gè)數(shù)黃豆的笨辦法，大到國(guó)家的民意測(cè)驗(yàn)，小到中子的移動(dòng)軌跡，從金融市場(chǎng)的風(fēng)險(xiǎn)分析，到軍事演習(xí)的沙盤(pán)推演，蒙特卡洛方法無(wú)處不在背后發(fā)揮著它的神奇威力。

蒙特卡洛方法由美國(guó)拉斯阿莫斯國(guó)家實(shí)驗(yàn)室的三位科學(xué)家John von Neumann（看清楚了，這位可是馮諾伊曼同志?。?Stan Ulam 和 Nick Metropolis共同發(fā)明。就其本質(zhì)而言，蒙特卡洛方法是用類(lèi)似于物理實(shí)驗(yàn)的近似方法求解問(wèn)題，它的魔力在于，對(duì)于那些規(guī)模極大的問(wèn)題，求解難度隨著問(wèn)題的維數(shù)（自變量個(gè)數(shù)）的增加呈指數(shù)級(jí)別增長(zhǎng)，出現(xiàn)所謂的“維數(shù)的災(zāi)難”（Course of Dimensionality）。對(duì)此，傳統(tǒng)方法無(wú)能為力，而蒙特卡洛方法卻可以獨(dú)辟蹊徑，基于隨機(jī)仿真的過(guò)程給出近似的結(jié)果。

最后八卦一下，Monte Carlo這個(gè)名字是怎么來(lái)的？它是摩納哥的一座以博彩業(yè)聞名的城市，賭博其實(shí)是門(mén)概率的高深學(xué)問(wèn)，不是么？

1947 單純形法

單純形法是由大名鼎鼎的“預(yù)測(cè)未來(lái)”的蘭德公司的Grorge Dantzig發(fā)明的，它成為線性規(guī)劃學(xué)科的重要基石。所謂線性規(guī)劃，簡(jiǎn)單的說(shuō)，就是給定一組線性（所有變量都是一次冪）約束條件（例如a1*x1 b1*x2 c1*x3>0)，求一個(gè)給定的目標(biāo)函數(shù)的極值。這么說(shuō)似乎也太太太抽象了，但在現(xiàn)實(shí)中能派上用場(chǎng)的例子可不罕見(jiàn)mdash;mdash;比如對(duì)于一個(gè)公司而言，其能夠投入生產(chǎn)的人力物力有限（ldquo;線性約束條件rdquo;），而公司的目標(biāo)是利潤(rùn)最大化（ldquo;目標(biāo)函數(shù)取最大值rdquo;），看，線性規(guī)劃并不抽象吧！線性規(guī)劃作為運(yùn)籌學(xué)(operation research)的一部分，成為管理科學(xué)領(lǐng)域的一種重要工具。而Dantzig提出的單純形法便是求解類(lèi)似線性規(guī)劃問(wèn)題的一個(gè)極其有效的方法，說(shuō)來(lái)慚愧，本科二年級(jí)的時(shí)候筆者也學(xué)過(guò)一學(xué)期的運(yùn)籌學(xué)，現(xiàn)在腦子里能想起的居然只剩下單純形法了mdash;mdash;不過(guò)這不也正說(shuō)明了該方法的簡(jiǎn)單和直觀么？

順便說(shuō)句題外話，寫(xiě)過(guò)《萬(wàn)歷十五年》的黃仁宇曾說(shuō)中國(guó)的傳統(tǒng)是“不能從數(shù)目字上管理”，我們習(xí)慣于“拍腦袋”，而不是基于嚴(yán)格的數(shù)據(jù)做決定，也許改變這一傳統(tǒng)的方法之一就是全

民動(dòng)員學(xué)習(xí)線性規(guī)劃喔。

1950 Krylov子空間迭代法

1951 矩陣計(jì)算的分解方法

50年代初的這兩個(gè)算法都是關(guān)于線性代數(shù)中的矩陣計(jì)算的，看到數(shù)學(xué)就頭大的讀者恐怕看到算法的名字已經(jīng)開(kāi)始皺眉毛了。Krylov子空間疊代法是用來(lái)求解形如Ax=b 的方程，A是一個(gè)n*n 的矩陣，當(dāng)n充分大時(shí)，直接計(jì)算變得非常困難，而Krylov方法則巧妙地將其變?yōu)镵xi 1=Kxi b-Axi的迭代形式來(lái)求解。這里的K(來(lái)源于作者俄國(guó)人Nikolai Krylov姓氏的首字母)是一個(gè)構(gòu)造出來(lái)的接近于A的矩陣，而迭代形式的算法的妙處在于，它將復(fù)雜問(wèn)題化簡(jiǎn)為階段性的易于計(jì)算的子步驟。

1951年由橡樹(shù)嶺國(guó)家實(shí)驗(yàn)室的AlstonHouseholder提出的矩陣計(jì)算的分解方法，則證明了任何矩陣都可以分解為三角、對(duì)角、正交和其他特殊形式的矩陣，該算法的意義使得開(kāi)發(fā)靈活的矩陣計(jì)算軟件包成為可能。

1957 優(yōu)化的Fortran編譯器

說(shuō)實(shí)話，在這份學(xué)術(shù)氣息無(wú)比濃郁的榜單里突然冒出一個(gè)編譯器(Compiler)如此工程化的東東實(shí)在讓人有“關(guān)公戰(zhàn)秦瓊”的感覺(jué)。不過(guò)換個(gè)角度想想，F(xiàn)ortran這一門(mén)幾乎為科學(xué)計(jì)算度身定制的編程語(yǔ)言對(duì)于科學(xué)家（尤其是數(shù)學(xué)家，物理學(xué)家）們實(shí)在是太重要了，簡(jiǎn)直是他們形影不離的一把瑞士軍刀，這也難怪他們紛紛搶著要把票投給了它。要知道，F(xiàn)ortran是第一種能將數(shù)學(xué)公式轉(zhuǎn)化為計(jì)算機(jī)程序的高級(jí)語(yǔ)言，它的誕生使得科學(xué)家們真正開(kāi)始利用計(jì)算機(jī)作為計(jì)算工具為他們的研究服務(wù)，這是計(jì)算機(jī)應(yīng)用技術(shù)的一個(gè)里程碑級(jí)別的貢獻(xiàn)。

話說(shuō)回來(lái)，當(dāng)年這幫開(kāi)發(fā)Fortran的家伙真是天才——只用23500行匯編指令就完成了一個(gè)Fortran編譯器，而且其效率之高令人嘆為觀止:當(dāng)年在IBM 主持這一項(xiàng)目的負(fù)責(zé)人JohnBackus在數(shù)十年后，回首這段往事的時(shí)候也感慨，說(shuō)它生成代碼的效率“出乎了所有開(kāi)發(fā)者的想象”。看來(lái)作為程序員，自己寫(xiě)的程序跑起來(lái)“出乎自己的想象”，有時(shí)候還真不一定是件壞事！

1959-61 計(jì)算矩陣特征值的QR算法

呼，又是一個(gè)和線性代數(shù)有關(guān)的算法，學(xué)過(guò)線性代數(shù)的應(yīng)該還記得“矩陣的特征值”吧？計(jì)算特征值是矩陣計(jì)算的最核心內(nèi)容之一，傳統(tǒng)的求解方案涉及到高次方程求根，當(dāng)問(wèn)題規(guī)模大的時(shí)候十分困難。QR算法把矩陣分解成一個(gè)正交矩陣（什么是正交矩陣？！還是趕緊去翻書(shū)吧?。┡c一個(gè)上三角矩陣的積，和前面提到的 Krylov 方法類(lèi)似，這又是一個(gè)迭代算法，它把復(fù)雜的高次方程求根問(wèn)題化簡(jiǎn)為階段性的易于計(jì)算的子步驟，使得用計(jì)算機(jī)求解大規(guī)模矩陣特征值成為可能。這個(gè)算法的作者是來(lái)自英國(guó)倫敦的J.G.F.Francis。

1962 快速排序算法

不少讀者恐怕和我一樣,看到“快速排序算法（”Quick Sort）這個(gè)條目時(shí),心里的感覺(jué)是——“這可總算找到組織了”。相比于其他一些對(duì)程序員而言高深莫測(cè)的數(shù)學(xué)物理公式,快速排序算法

真是我們朝夕相處的好伙伴——老板讓你寫(xiě)個(gè)排序算法,如果你寫(xiě)出來(lái)的不是快速排序,你都不好意思跟同事打招呼。其實(shí)根本不用自己動(dòng)手實(shí)現(xiàn), 不論是ANSI C,C STL,還是Java SDK,天下幾乎所有的SDK里都能找到它的某種實(shí)現(xiàn)版本。

快速排序算法最早由Tony Hoare爵士設(shè)計(jì)，它的基本思想是將待排序列分為兩半，左邊的一半總是“小的”，右邊的一半總是“大的”，這一過(guò)程不斷遞歸持續(xù)下去，直到整個(gè)序列有序。說(shuō)起這位Tony Hoare爵士，快速排序算法其實(shí)只是他不經(jīng)意間的小小發(fā)現(xiàn)而已，他對(duì)于計(jì)算機(jī)貢獻(xiàn)主要包括形式化方法理論，以及ALGOL60 編程語(yǔ)言的發(fā)明等，他也因這些成就獲得1980 年圖靈獎(jiǎng)。

快速排序的平均時(shí)間復(fù)雜度僅僅為O(Nlog(N))，相比于普通選擇排序和冒泡排序等而言，實(shí)在是歷史性的創(chuàng)舉。

1965 快速傅立葉變換（FFT）

如果要評(píng)選對(duì)我們的日常生活影響最大的算法，快速傅立葉變換算法應(yīng)該是當(dāng)仁不讓的總冠軍——每天當(dāng)拿起話筒，打開(kāi)手機(jī)，聽(tīng)mp3，看DVD，用DC拍照 ——毫不夸張的說(shuō)，哪里有數(shù)字信號(hào)處理，哪里就有快速傅立葉變換。快速傅立葉算法是離散傅立葉算法（這可是數(shù)字信號(hào)處理的基石）的一種快速算法，它有 IBM 華生研究院的James Cooley和普林斯頓大學(xué)的John Tukey共同提出，其時(shí)間復(fù)雜度僅為O(Nlog(N))；比時(shí)間效率更為重要的是，快速傅立葉算法非常容易用硬件實(shí)現(xiàn)，因此它在電子技術(shù)領(lǐng)域得到極其廣泛的應(yīng)用。

1977 整數(shù)關(guān)系探測(cè)算法

整數(shù)關(guān)系探測(cè)是個(gè)古老的問(wèn)題，其歷史甚至可以追溯到歐幾里德的時(shí)代。具體的說(shuō):

給定—組實(shí)數(shù)X1,X2,...,Xn，是否存在不全為零的整數(shù)a1,a2,...an，使得:a 1 x 1 a 2 x 2...a n x n ＝ 0 這一年BrighamYoung大學(xué)的Helaman Ferguson 和Rodney Forcade解決了這一問(wèn)題。至于這個(gè)算法的意義嘛，呃，該算法應(yīng)用于“簡(jiǎn)化量子場(chǎng)論中的Feynman圖的計(jì)算”——太深?yuàn)W的學(xué)問(wèn)拉！

1987 快速多極算法

日歷翻到了1987 年，這一年的算法似乎更加玄奧了，耶魯大學(xué)的Leslie Greengard和Vladimir Rokhlin提出的快速多極算法用來(lái)計(jì)算“經(jīng)由引力或靜電力相互作用的N 個(gè)粒子運(yùn)動(dòng)的精確計(jì)算——例如銀河系中的星體，或者蛋白質(zhì)中的原子間的相互作用”，天哪，不是我不明白，這世界真是變得快！