什么是算法?

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

可以這樣理解，算法是用來解決特定問題的一系列步驟(不僅計(jì)算機(jī)需要算法，我們?cè)谌粘Ｉ钪幸苍谑褂盟惴?。算法必須具備如下3個(gè)重要特性：

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

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

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

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

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

1 排序算法

所謂排序，就是使一串記錄，按照其中的某個(gè)或某些關(guān)鍵字的大小，遞增或遞減的排列起來的操作。排序算法，就是如何使得記錄按照要求排列的方法。排序算法在很多領(lǐng)域得到相當(dāng)?shù)刂匾?，尤其是在大量?shù)據(jù)的處理方面。一個(gè)優(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) 額外空間

計(jì)數(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)期望時(shí)間;O(n^2)最壞時(shí)間;需要 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) 期望時(shí)間，O(n^2) 最壞情況;對(duì)于大的、亂數(shù)列表一般相信是最快的已知排序

Introsort—O(nlog n)

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

不實(shí)用的

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

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

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

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

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

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

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

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

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

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

用正余弦來表示原信號(hào)會(huì)更加簡(jiǎn)單，因?yàn)檎嘞覔碛性盘?hào)所不具有的性質(zhì)：正弦曲線保真度。一個(gè)正余弦曲線信號(hào)輸入后，輸出的仍是正余弦曲線，只有幅度和相位可能發(fā)生變化，但是頻率和波的形狀仍是一樣的。且只有正余弦曲線才擁有這樣的性質(zhì)，正因如此我們才不用方波或三角波來表示。

3 Dijkstra 算法

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

4 RSA算法變換

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

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

5 安全哈希算法

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

6 整數(shù)因式分解

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

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

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

7 鏈接分析

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

8 比例積分微分算法

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

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

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

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

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

10 隨機(jī)數(shù)生成

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