編者薦語

文章基于《統(tǒng)治世界的十大算法》進行了系統(tǒng)性的整理,其作者George Dvorsky試圖解釋算法之于當今世界的重要性,以及哪些算法對人類文明做出過巨大的貢獻。

1 排序算法  

所謂排序,就是使一串記錄,按照其中的某個或某些關(guān)鍵字的大小,遞增或遞減的排列起來的操作。排序算法,就是如何使得記錄按照要求排列的方法。排序算法在很多領(lǐ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ù)表示成三角函數(shù)(正弦和/或余弦函數(shù))或者它們的積分的線性組合。在不同的研究領(lǐng)域,傅立葉變換具有多種不同的變體形式,如連續(xù)傅立葉變換和離散傅立葉變換。傅立葉是一位法國數(shù)學家和物理學家,原名是JeanBaptiste Joseph Fourier(1768-1830), Fourier于1807年在法國科學學會上發(fā)表了一篇論文,論文里描述運用正弦曲線來描述溫度分布,論文里有個在當時具有爭議性的決斷:任何連續(xù)周期信號都可以由一組適當?shù)恼�弦曲線組合而成。當時審查這個論文拉格朗日堅決反對此論文的發(fā)表,而后在近50年的時間里,拉格朗日堅持認為傅立葉的方法無法表示帶有棱角的信號,如在方波中出現(xiàn)非連續(xù)變化斜率。直到拉格朗日死后15年這個論文才被發(fā)表出來。誰是對的呢?拉格朗日是對的:正弦曲線無法組合成一個帶有棱角的信號。但是,我們可以用正弦曲線來非常逼近地表示它,逼近到兩種表示方法不存在能量差別,基于此,傅立葉是對的。為什么我們要用正弦曲線來代替原來的曲線呢?如我們也還可以用方波或三角波來代替呀,分解信號的方法是無窮多的,但分解信號的目的是為了更加簡單地處理原來的信號。

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

3 Dijkstra 算法  

Dijkstra算法算是貪心思想實現(xiàn)的,首先把起點到所有點的距離存下來找個最短的,然后松弛一次再找出最短的,所謂的松弛操作就是,遍歷一遍看通過剛剛找到的距離最短的點作為中轉(zhuǎn)站會不會更近,如果更近了就更新距離,這樣把所有的點找遍之后就存下了起點到其他所有點的最短距離。
問題引入:

指定一個點(源點)到其余各個頂點的最短路徑,也叫做“單源最短路徑”。例如求下圖中的1號頂點到2、3、4、5、6號頂點的最短路徑。

下面我們來模擬一下:

這就是Dijkstra算法的基本思路。

4 RSA算法

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

一、公鑰加密算法是什么?

公鑰加密,非對稱加密。簡單的說,就是明文通過公鑰加密,但只能通過密鑰來解密。假設(shè)機器A需要向機器B傳送一段極隱私的數(shù)據(jù),要求只有機器B能解密,就需要機器B生成一對密鑰,其中公鑰向包括機器A在內(nèi)的所有人公布,那機器A就可以用公鑰加密傳送的數(shù)據(jù),機器B接收到之后用私鑰解密,其他人沒有私鑰,即使捕獲到機器A發(fā)送的消息,也無法解密。

二、 RSA實現(xiàn)基本思路

RSA公鑰密碼體制描述如下:(m為明文,c為密文)

1． 選取兩個大素數(shù)p,q。p和q保密

2． 計算n=pq,r=(p-1)(q-1)。n公開,r保密

3． 隨機選取正整數(shù)1

4． 計算d,滿足de=1(mod r)．d是保密的解密密鑰

5． 加密變換:　　c=m^e mod n

6． 解密變換:　　m=c^d mod n

三、 RSA為什么能用公鑰加密,私鑰解密?

RSA算法基于一個十分簡單的數(shù)論事實:將兩個大素數(shù)相乘十分容易,但是想要對其乘積進行因式分解卻極其困難,因此可以將乘積公開作為加密密鑰。

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

5 安全哈希算法  

安全哈希(散列)算法(Secure Hash Algorithm,SHA)是一個密碼散列函數(shù)家族,是FIPS所認證的安全散列算法。能計算出一個數(shù)字消息所對應到的,長度固定的字符串(又稱消息摘要)的算法。且若輸入的消息不同,它們對應到不同字符串的機率很高。SHA家族的五個算法,分別是SHA-1、SHA-224、SHA-256、SHA-384,和SHA-512,由美國國家安全局(NSA)所設(shè)計,并由美國國家標準與技術(shù)研究院(NIST)發(fā)布;是美國的政府標準。后四者有時并稱為SHA-2。SHA-1在許多安全協(xié)定中廣為使用,包括TLS和SSL、PGP、SSH、S/MIME和IPsec,曾被視為是MD5(更早之前被廣為使用的雜湊函數(shù))的后繼者。但SHA-1的安全性如今被密碼學家嚴重質(zhì)疑;雖然至今尚未出現(xiàn)對SHA-2有效的攻擊,它的算法跟SHA-1基本上仍然相似;因此有些人開始發(fā)展其他替代的雜湊算法。
簡單的文字描述服務端:后臺接口接受相關(guān)參數(shù),然后將(A,B)在后臺進行SHA1加密,獲取加密摘要D,最后將D與C進行比較,如果C == D ,則A和B在傳輸過程中參數(shù)沒有被竊取改變;如果C != D,則說明A和B已經(jīng)在傳輸過程中發(fā)生了改變,最好不要使用。
客戶端:
在APP與后端服務器接口調(diào)用的時候,將需要傳輸?shù)膮��?shù)進行關(guān)鍵參數(shù)(如:String A,String B)進行SHA1加密,獲取加密之后的摘要(C);然后在接口調(diào)用的時候?qū)�參�?shù)原文(A,B)和加密的摘要(C)一起傳輸給后臺服務器。

6 整數(shù)因式分解  

整數(shù)因式分解是在計算機領(lǐng)域被大量使用的數(shù)學算法,沒有這個算法,信息加密會更不安全。該算法定義了一系列步驟,得到將一合數(shù)分解為更小因子的質(zhì)數(shù)分解式。這被認為是一種FNP問題,它是NP分類問題的延伸,極其難以解決。許多加密協(xié)議(如RSA算法)都基于這樣一個原理。相對于素數(shù)判定來說,因式分解的實現(xiàn)就沒辦法達到那么快速了。因子分解至今仍沒有類似于素數(shù)判定的多項式算法,這也成為了RSA公鑰系統(tǒng)安全得以保障的基礎(chǔ)。如果一個算法能夠快速地對任意整數(shù)進行因式分解,RSA的公鑰加密體系就會失去其安全性。鑒于這兩個問題的難度相差較大,在我們施行分解之前,最好是預先知道目標整數(shù)的確不是一個素數(shù),否則很可能花費了很大力氣只干了素數(shù)判定的活 ——殺雞用牛刀了。

因式分解的分為一般方法和特殊方法兩大類,通常傾向于先針對數(shù)的特殊性,使用對應的特殊方法,如果目標數(shù)的形式不那么特殊,再嘗試使用一般方法。當然,前者往往要比后者快上許多。

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

7 鏈接分析算法  

常見的鏈接分析算法除了鼎鼎有名的PageRank,還有HITS、SALSA、Hilltop以及主題PageRank等等。需要重點理解的是PageRank和HITS,后面這些算法都是以它們?yōu)榛�礎(chǔ)的。

絕大部分鏈接分析算法建立在兩個概念模型,它們是:

隨機游走模型:

針對瀏覽網(wǎng)頁用戶行為建立的抽象概念模型,用戶上網(wǎng)過程中會不斷打開鏈接,在相互有鏈接指向的網(wǎng)頁之間跳轉(zhuǎn),這是直接跳轉(zhuǎn),如果某個頁面包含的所有鏈接用戶都不感興趣則可能會在瀏覽器中輸入另外的網(wǎng)址,這是遠程跳轉(zhuǎn)。該模型就是對一個直接跳轉(zhuǎn)和遠程跳轉(zhuǎn)兩種用戶瀏覽行為進行抽象的概念模型;典型的使用該模型的算法是PageRank;

子集傳播模型:

基本思想是把互聯(lián)網(wǎng)網(wǎng)頁按照一定規(guī)則劃分,分為兩個甚至是多個子集合。其中某個子集合具有特殊性質(zhì),很多算法從這個具有特殊性質(zhì)的子集合出發(fā),給予子集合內(nèi)網(wǎng)頁初始權(quán)值,之后根據(jù)這個特殊子集合內(nèi)網(wǎng)頁和其他網(wǎng)頁的鏈接關(guān)系,按照一定方式將權(quán)值傳遞到其他網(wǎng)頁。典型的使用該模型的算法有HITS和Hilltop算法。

從圖中可看出,在眾多算法中,PageRank和HITS算法可以說是最重要的兩個具有代表性的鏈接分析算法,后續(xù)的很多鏈接分析算法都是在這兩個算法基礎(chǔ)上衍生出來的改進算法。

8 PID(比例積分微分)算法  

你是否曾經(jīng)用過飛機、汽車、衛(wèi)星服務或手機網(wǎng)絡?你是否曾經(jīng)在工廠工作或是看見過機器人?如果回答是肯定的,那么你應該已經(jīng)見識過這個算法了。大體上,這個算法使用一種控制回路反饋機制,將期望輸出信號和實際輸出信號之間的錯誤最小化。無論何處,只要你需要進行信號處理,或者你需要一套電子系統(tǒng),用來自動化控制機械、液壓或熱力系統(tǒng),這個算法都會有用武之地。
PID即:Proportional(比例)、Integral(積分)、Differential(微分)的縮寫。顧名思義,PID控制算法是結(jié)合比例、積分和微分三種環(huán)節(jié)于一體的控制算法,它是連續(xù)系統(tǒng)中技術(shù)最為成熟、應用最為廣泛的一種控制算法,該控制算法出現(xiàn)于20世紀30至40年代,適用于對被控對象模型了解不清楚的場合。實際運行的經(jīng)驗和理論的分析都表明,運用這種控制規(guī)律對許多工業(yè)過程進行控制時,都能得到比較滿意的效果。PID控制的實質(zhì)就是根據(jù)輸入的偏差值,按照比例、積分、微分的函數(shù)關(guān)系進行運算,運算結(jié)果用以控制輸出。
在工業(yè)過程中,連續(xù)控制系統(tǒng)的理想PID控制規(guī)律為:

式中,Kp——比例增益,Kp與比例度成倒數(shù)關(guān)系;

Tt——積分時間常數(shù);

TD——微分時間常數(shù);

u(t)——PID控制器的輸出信號;

e(t)——給定值r(t)與測量值之差。

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

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

在現(xiàn)今的電子信息技術(shù)領(lǐng)域,正發(fā)生著一場有長遠影響的數(shù)字化革命。由于數(shù)字化的多媒體信息尤其是數(shù)字視頻、音頻信號的數(shù)據(jù)量特別龐大,如果不對其進行有效的壓縮就難以得到實際的應用。因此,數(shù)據(jù)壓縮算法已成為當今數(shù)字通信、廣播、存儲和多媒體娛樂中的一項關(guān)鍵的共性技術(shù)。用于多媒體數(shù)據(jù)的壓縮方法眾多,可按主要特點將它們分成不同的類型:
(1)無損與有損1、無損壓縮:能夠無失真地從壓縮后的數(shù)據(jù)重構(gòu),準確地還原原始數(shù)據(jù)�？捎糜趯�數(shù)據(jù)的準確性要求嚴格的場合,如可執(zhí)行文件和普通文件的壓縮、磁盤的壓縮,也可用于多媒體數(shù)據(jù)的壓縮。該方法的壓縮比較小。如差分編碼、RLE、Huffman編碼、LZW編碼、算術(shù)編碼。2、有損壓縮:有失真,不能完全準確地恢復原始數(shù)據(jù),重構(gòu)的數(shù)據(jù)只是原始數(shù)據(jù)的一個近似。可用于對數(shù)據(jù)的準確性要求不高的場合,如多媒體數(shù)據(jù)的壓縮。該方法的壓縮比較大。例如預測編碼、音感編碼、分形壓縮、小波壓縮、JPEG/MPEG。
(2)對稱性若編解碼算法的復雜性和所需時間差不多,則為對稱的編碼方法,多數(shù)壓縮算法都是對稱的。但也有不對稱的,一般是編碼難而解碼容易,如Huffman編碼和分形編碼。但用于密碼學的編碼方法則相反,是編碼容易,而解碼則非常難。
(3)幀間與幀內(nèi)在視頻編碼中會同時用到幀內(nèi)與幀間的編碼方法,幀內(nèi)編碼是指在一幀圖像內(nèi)獨立完成的編碼方法,同靜態(tài)圖像的編碼,如JPEG;而幀間編碼則需要參照前后幀才能進行編解碼,并在編碼過程中考慮對幀之間的時間冗余的壓縮,如MPEG。
(4)實時性在有些多媒體的應用場合,需要實時處理或傳輸數(shù)據(jù)(如現(xiàn)場的數(shù)字錄音和錄影、播放MP3/RM/VCD/DVD、視頻/音頻點播、網(wǎng)絡現(xiàn)場直播、可視電話、視頻會議),編解碼一般要求延時≤50ms。這就需要簡單/快速/高效的算法和高速/復雜的CPU/DSP芯片。
(5)分級處理有些壓縮算法可以同時處理不同分辨率、不同傳輸速率、不同質(zhì)量水平的多媒體數(shù)據(jù),如JPEG2000、MPEG-2/4。

10 隨機數(shù)生成  

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

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

產(chǎn)生隨機數(shù)有多種不同的方法。這些方法被稱為隨機數(shù)發(fā)生器。隨機數(shù)最重要的特性是:它所產(chǎn)生的后面的那個數(shù)與前面的那個數(shù)毫無關(guān)系。