什么是算法?

簡而言之，任何定義明確的計算步驟都可稱為算法，接受一個或一組值為輸入，輸出一個或一組值。(來源：homas H. Cormen, Chales E. Leiserson 《算法導(dǎo)論第3版》)

可以這樣理解，算法是用來解決特定問題的一系列步驟(不僅計算機需要算法，我們在日常生活中也在使用算法)。算法必須具備如下3個重要特性：

有窮性，執(zhí)行有限步驟后，算法必須中止。

確切性，算法的每個步驟都必須確切定義。

可行性，特定算法須可以在特定的時間內(nèi)解決特定問題，

其實，算法雖然廣泛應(yīng)用在計算機領(lǐng)域，但卻完全源自數(shù)學(xué)。實際上，最早的數(shù)學(xué)算法可追溯到公元前1600年-Babylonians有關(guān)求因式分解和平方根的算法。

一 篇有趣的文章《統(tǒng)治世界的十大算法》中，作者George Dvorsky試圖解釋算法之于當(dāng)今世界的重要性，以及哪些算法對人類文明最為重要。

1 排序算法

所謂排序，就是使一串記錄，按照其中的某個或某些關(guān)鍵字的大小，遞增或遞減的排列起來的操作。排序算法，就是如何使得記錄按照要求排列的方法。排序算法在很多領(lǐng)域得到相當(dāng)?shù)刂匾?，尤其是在大量?shù)據(jù)的處理方面。一個優(yōu)秀的算法可以節(jié)省大量的資源。

穩(wěn)定的

冒泡排序(bubble sort) — O(n^2)

雞尾酒排序(Cocktail sort，雙向的冒泡排序) — O(n^2)

插入排序(insertion sort)— O(n^2)

桶排序(bucket sort)— O(n); 需要 O(k) 額外空間

計數(shù)排序(counting sort) — O(n+k); 需要 O(n+k) 額外空間

合并排序(merge sort)— O(nlog n);需要 O(n) 額外空間

原地合并排序— O(n^2)

二叉排序樹排序 (Binary tree sort) — O(nlog n)期望時間;O(n^2)最壞時間;需要 O(n) 額外空間

鴿巢排序(Pigeonhole sort)— O(n+k); 需要 O(k) 額外空間

基數(shù)排序(radix sort)— O(n·k); 需要 O(n) 額外空間

Gnome 排序— O(n^2)

圖書館排序— O(nlog n) withhigh probability，需要(1+ε)n額外空間

不穩(wěn)定的

選擇排序(selection sort)— O(n^2)

希爾排序(shell sort)— O(nlog n) 如果使用最佳的現(xiàn)在版本

組合排序— O(nlog n)

堆排序(heapsort)— O(nlog n)

平滑排序— O(nlog n)

快速排序(quicksort)— O(nlog n) 期望時間，O(n^2) 最壞情況;對于大的、亂數(shù)列表一般相信是最快的已知排序

Introsort—O(nlog n)

Patience sorting— O(nlog n+k) 最壞情況時間，需要額外的 O(n+ k) 空間，也需要找到最長的遞增子串行(longest increasing subsequence)

不實用的

Bogo排序— O(n× n!) 期望時間，無窮的最壞情況。

Stupid sort— O(n^3); 遞歸版本需要 O(n^2)額外存儲器

珠排序(Bead sort) — O(n) or O(√n)，但需要特別的硬件

Pancake sorting— O(n)，但需要特別的硬件

stooge sort——O(n^2.7)很漂亮但是很耗時

2 傅立葉變換與快速傅立葉變換

傅立葉是一位法國數(shù)學(xué)家和物理學(xué)家，原名是JeanBaptiste Joseph Fourier(1768-1830), Fourier于1807年在法國科學(xué)學(xué)會上發(fā)表了一篇論文，論文里描述運用正弦曲線來描述溫度分布，論文里有個在當(dāng)時具有爭議性的決斷：任何連續(xù)周期信號都可以由一組適當(dāng)?shù)恼仪€組合而成。

當(dāng)時審查這個論文拉格朗日堅決反對此論文的發(fā)表，而后在近50年的時間里，拉格朗日堅持認(rèn)為傅立葉的方法無法表示帶有棱角的信號，如在方波中出現(xiàn)非連續(xù)變化斜率。直到拉格朗日死后15年這個論文才被發(fā)表出來。

誰是對的呢?拉格朗日是對的：正弦曲線無法組合成一個帶有棱角的信號。但是，我們可以用正弦曲線來非常逼近地表示它，逼近到兩種表示方法不存在能量差別，基于此，傅立葉是對的。

為什么我們要用正弦曲線來代替原來的曲線呢?如我們也還可以用方波或三角波來代替呀，分解信號的方法是無窮多的，但分解信號的目的是為了更加簡單地處理原來的信號。

用正余弦來表示原信號會更加簡單，因為正余弦擁有原信號所不具有的性質(zhì)：正弦曲線保真度。一個正余弦曲線信號輸入后，輸出的仍是正余弦曲線，只有幅度和相位可能發(fā)生變化，但是頻率和波的形狀仍是一樣的。且只有正余弦曲線才擁有這樣的性質(zhì)，正因如此我們才不用方波或三角波來表示。

3 Dijkstra 算法

Dijkstra算法是典型的算法。Dijkstra算法是很有代表性的算法。Dijkstra一般的表述通常有兩種方式，一種用永久和臨時標(biāo)號方式，一種是用OPEN, CLOSE表的方式，這里均采用永久和臨時標(biāo)號的方式。注意該算法要求圖中不存在負(fù)權(quán)邊。

4 RSA算法變換

RSA是目前最有影響力的公鑰加密算法，它能夠抵抗到目前為止已知的絕大多數(shù)密碼攻擊，已被ISO推薦為公鑰數(shù)據(jù)加密標(biāo)準(zhǔn)。

今天只有短的RSA鑰匙才可能被強力方式解破。到2008年為止，世界上還沒有任何可靠的攻擊RSA算法的方式。只要其鑰匙的長度足夠長，用RSA加密的信息實際上是不能被解破的。但在分布式計算和量子計算機理論日趨成熟的今天，RSA加密安全性受到了挑戰(zhàn)。

5 安全哈希算法

一種對輸入信息(例如消息)進行摘要的算法。摘要過程能夠完成下列特點：不同的輸入信息絕對不會具有相同的指紋：相近輸入信息經(jīng)過摘要之后的輸出信息具有較大的差異，同時計算上很難生產(chǎn)一個與給定輸入具有相同指紋的輸入。(即不可逆)。

6 整數(shù)因式分解

這是在計算機領(lǐng)域被大量使用的數(shù)學(xué)算法，沒有這個算法，信息加密會更不安全。該算法定義了一系列步驟，得到將一合數(shù)分解為更小因子的質(zhì)數(shù)分解式。這被認(rèn)為是一種FNP問題，它是NP分類問題的延伸，極其難以解決。

許多加密協(xié)議(如RSA算法)都基于這樣一個原理：對大的合數(shù)作因式分解是非常困難的。如果一個算法能夠快速地對任意整數(shù)進行因式分解，RSA的公鑰加密體系就會失去其安全性。

量子計算的誕生使我們能夠更容易地解決這類問題，同時它也打開了一個全新的領(lǐng)域，使得我們能夠利用量子世界中的特性來保證系統(tǒng)安全。

7 鏈接分析

鏈接分析，源于對Web結(jié)構(gòu)中超鏈接的多維分析。當(dāng)前其應(yīng)用主要體現(xiàn)在網(wǎng)絡(luò)信息檢索、網(wǎng)絡(luò)計量學(xué)、數(shù)據(jù)挖掘、Web結(jié)構(gòu)建模等方山。作為Google的核心技術(shù)之一，鏈接分析算法應(yīng)用已經(jīng)顯現(xiàn)出j驚人的商業(yè)價值。

8 比例積分微分算法

你是否曾經(jīng)用過飛機、汽車、衛(wèi)星服務(wù)或手機網(wǎng)絡(luò)?你是否曾經(jīng)在工廠工作或是看見過機器人?如果回答是肯定的，那么你應(yīng)該已經(jīng)見識過這個算法了。

大體上，這個算法使用一種控制回路反饋機制，將期望輸出信號和實際輸出信號之間的錯誤最小化。無論何處，只要你需要進行信號處理，或者你需要一套電子系統(tǒng)，用來自動化控制機械、液壓或熱力系統(tǒng)，這個算法都會有用武之地。

可以這樣說，如果沒有這個算法，現(xiàn)代文明將不復(fù)存在。

9 數(shù)據(jù)壓縮算法

在現(xiàn)今的電子信息技術(shù)領(lǐng)域，正發(fā)生著一場有長遠影響的數(shù)字化革命。由于數(shù)字化的多媒體信息尤其是數(shù)字視頻、音頻信號的數(shù)據(jù)量特別龐大，如果不對其進行有效的壓縮就難以得到實際的應(yīng)用。因此，數(shù)據(jù)壓縮技術(shù)已成為當(dāng)今數(shù)字通信、廣播、存儲和多媒體娛樂中的一項關(guān)鍵的共性技術(shù)。

10 隨機數(shù)生成

在統(tǒng)計學(xué)的不同技術(shù)中需要使用隨機數(shù)，比如在從統(tǒng)計總體中抽取有代表性的樣本的時候，或者在將實驗動物分配到不同的試驗組的過程中，或者在進行蒙特卡羅模擬法計算的時候等等。