作者 | George Dvorsky

編譯 | 深度學(xué)習(xí)這件小事

1 排序算法

所謂排序，就是使一串記錄，按照其中的某個(gè)或某些關(guān)鍵字的大小，遞增或遞減的排列起來(lái)的操作。排序算法，就是如何使得記錄按照要求排列的方法。排序算法在很多領(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í)間，無(wú)窮的最壞情況。
• 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 傅立葉變換與快速傅立葉變換

傅立葉是一位法國(guó)數(shù)學(xué)家和物理學(xué)家，原名是JeanBaptiste Joseph Fourier(1768-1830), Fourier于1807年在法國(guó)科學(xué)學(xué)會(huì)上發(fā)表了一篇論文，論文里描述運(yùn)用正弦曲線來(lái)描述溫度分布，論文里有個(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)為傅立葉的方法無(wú)法表示帶有棱角的信號(hào)，如在方波中出現(xiàn)非連續(xù)變化斜率。直到拉格朗日死后15年這個(gè)論文才被發(fā)表出來(lái)。誰(shuí)是對(duì)的呢？拉格朗日是對(duì)的：正弦曲線無(wú)法組合成一個(gè)帶有棱角的信號(hào)。但是，我們可以用正弦曲線來(lái)非常逼近地表示它，逼近到兩種表示方法不存在能量差別，基于此，傅立葉是對(duì)的。為什么我們要用正弦曲線來(lái)代替原來(lái)的曲線呢？如我們也還可以用方波或三角波來(lái)代替呀，分解信號(hào)的方法是無(wú)窮多的，但分解信號(hào)的目的是為了更加簡(jiǎn)單地處理原來(lái)的信號(hào)。用正余弦來(lái)表示原信號(hào)會(huì)更加簡(jiǎn)單，因?yàn)檎嘞覔碛性盘?hào)所不具有的性質(zhì)：正弦曲線保真度。一個(gè)正余弦曲線信號(hào)輸入后，輸出的仍是正余弦曲線，只有幅度和相位可能發(fā)生變化，但是頻率和波的形狀仍是一樣的。且只有正余弦曲線才擁有這樣的性質(zhì)，正因如此我們才不用方波或三角波來(lái)表示。

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

5 安全哈希算法

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

6 整數(shù)因式分解

這是在計(jì)算機(jī)領(lǐng)域被大量使用的數(shù)學(xué)算法，沒(méi)有這個(gè)算法，信息加密會(huì)更不安全。該算法定義了一系列步驟，得到將一合數(shù)分解為更小因子的質(zhì)數(shù)分解式。這被認(rèn)為是一種FNP問(wèn)題，它是NP分類問(wèn)題的延伸，極其難以解決。許多加密協(xié)議（如RSA算法）都基于這樣一個(gè)原理：對(duì)大的合數(shù)作因式分解是非常困難的。如果一個(gè)算法能夠快速地對(duì)任意整數(shù)進(jìn)行因式分解，RSA的公鑰加密體系就會(huì)失去其安全性。量子計(jì)算的誕生使我們能夠更容易地解決這類問(wèn)題，同時(shí)它也打開了一個(gè)全新的領(lǐng)域，使得我們能夠利用量子世界中的特性來(lái)保證系統(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)用過(guò)飛機(jī)、汽車、衛(wèi)星服務(wù)或手機(jī)網(wǎng)絡(luò)？你是否曾經(jīng)在工廠工作或是看見(jiàn)過(guò)機(jī)器人？如果回答是肯定的，那么你應(yīng)該已經(jīng)見(jiàn)識(shí)過(guò)這個(gè)算法了。大體上，這個(gè)算法使用一種控制回路反饋機(jī)制，將期望輸出信號(hào)和實(shí)際輸出信號(hào)之間的錯(cuò)誤最小化。無(wú)論何處，只要你需要進(jìn)行信號(hào)處理，或者你需要一套電子系統(tǒng)，用來(lái)自動(dòng)化控制機(jī)械、液壓或熱力系統(tǒng)，這個(gè)算法都會(huì)有用武之地?？梢赃@樣說(shuō)，如果沒(méi)有這個(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ǔ)和多媒體娛樂(lè)中的一項(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)組的過(guò)程中，或者在進(jìn)行蒙特卡羅模擬法計(jì)算的時(shí)候等等。