作者 | George Dvorsky
編譯 | 深度學習這件小事
1 排序算法
所謂排序，就是使一串記錄，按照其中的某個或某些關鍵字的大小，遞增或遞減的排列起來的操作。排序算法，就是如何使得記錄按照要求排列的方法。排序算法在很多領域得到相當地重視，尤其是在大量數據的處理方面。一個優秀的算法可以節省大量的資源。
穩定的
- 冒泡排序（bubble sort） — O(n^2）
- 雞尾酒排序(Cocktail sort，雙向的冒泡排序) — O(n^2）
- 插入排序（insertion sort）— O(n^2)
- 桶排序（bucket sort）— O(n); 需要 O(k) 額外空間
- 計數排序(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) 額外空間
- 基數排序（radix sort）— O(n·k); 需要 O(n) 額外空間
- Gnome 排序— O(n^2)
- 圖書館排序— O(nlog n) withhigh probability，需要（1+ε)n額外空間
不穩定的
- 選擇排序（selection sort）— O(n^2)
- 希爾排序（shell sort）— O(nlog n) 如果使用最佳的現在版本
- 組合排序— O(nlog n)
- 堆排序（heapsort）— O(nlog n)
- 平滑排序— O(nlog n)
- 快速排序（quicksort）— O(nlog n) 期望時間，O(n^2) 最壞情況；對於大的、亂數列表一般相信是最快的已知排序
- 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 傅立葉變換與快速傅立葉變換
傅立葉是一位法國數學家和物理學家，原名是JeanBaptiste Joseph Fourier(1768-1830), Fourier於1807年在法國科學學會上發表了一篇論文，論文裡描述運用正弦曲線來描述溫度分佈，論文裡有個在當時具有爭議性的決斷：任何連續週期信號都可以由一組適當的正弦曲線組合而成。當時審查這個論文拉格朗日堅決反對此論文的發表，而後在近50年的時間裡，拉格朗日堅持認為傅立葉的方法無法表示帶有稜角的信號，如在方波中出現非連續變化斜率。直到拉格朗日死後15年這個論文才被髮表出來。誰是對的呢？拉格朗日是對的：正弦曲線無法組合成一個帶有稜角的信號。但是，我們可以用正弦曲線來非常逼近地表示它，逼近到兩種表示方法不存在能量差別，基於此，傅立葉是對的。為什麼我們要用正弦曲線來代替原來的曲線呢？如我們也還可以用方波或三角波來代替呀，分解信號的方法是無窮多的，但分解信號的目的是為了更加簡單地處理原來的信號。用正餘弦來表示原信號會更加簡單，因為正餘弦擁有原信號所不具有的性質：正弦曲線保真度。一個正餘弦曲線信號輸入後，輸出的仍是正餘弦曲線，只有幅度和相位可能發生變化，但是頻率和波的形狀仍是一樣的。且只有正餘弦曲線才擁有這樣的性質，正因如此我們才不用方波或三角波來表示。
3 Dijkstra 算法
Dijkstra算法是典型的算法。Dijkstra算法是很有代表性的算法。Dijkstra一般的表述通常有兩種方式，一種用永久和臨時標號方式，一種是用OPEN, CLOSE表的方式，這裡均採用永久和臨時標號的方式。注意該算法要求圖中不存在負權邊。
4 RSA算法變換
RSA是目前最有影響力的公鑰加密算法，它能夠抵抗到目前為止已知的絕大多數密碼攻擊，已被ISO推薦為公鑰數據加密標準。今天只有短的RSA鑰匙才可能被強力方式解破。到2008年為止，世界上還沒有任何可靠的攻擊RSA算法的方式。只要其鑰匙的長度足夠長，用RSA加密的信息實際上是不能被解破的。但在分佈式計算和量子計算機理論日趨成熟的今天，RSA加密安全性受到了挑戰。
5 安全哈希算法
一種對輸入信息（例如消息）進行摘要的算法。摘要過程能夠完成下列特點：不同的輸入信息絕對不會具有相同的指紋：相近輸入信息經過摘要之後的輸出信息具有較大的差異，同時計算上很難生產一個與給定輸入具有相同指紋的輸入。（即不可逆）。
6 整數因式分解
這是在計算機領域被大量使用的數學算法，沒有這個算法，信息加密會更不安全。該算法定義了一系列步驟，得到將一合數分解為更小因子的質數分解式。這被認為是一種FNP問題，它是NP分類問題的延伸，極其難以解決。許多加密協議（如RSA算法）都基於這樣一個原理：對大的合數作因式分解是非常困難的。如果一個算法能夠快速地對任意整數進行因式分解，RSA的公鑰加密體系就會失去其安全性。量子計算的誕生使我們能夠更容易地解決這類問題，同時它也打開了一個全新的領域，使得我們能夠利用量子世界中的特性來保證系統安全。
7 鏈接分析
鏈接分析，源於對Web結構中超鏈接的多維分析。當前其應用主要體現在網絡信息檢索、網絡計量學、數據挖掘、Web結構建模等方山。作為Google的核心技術之一，鏈接分析算法應用已經顯現出j驚人的商業價值。
8 比例積分微分算法
你是否曾經用過飛機、汽車、衛星服務或手機網絡？你是否曾經在工廠工作或是看見過機器人？如果回答是肯定的，那麼你應該已經見識過這個算法了。大體上，這個算法使用一種控制迴路反饋機制，將期望輸出信號和實際輸出信號之間的錯誤最小化。無論何處，只要你需要進行信號處理，或者你需要一套電子系統，用來自動化控制機械、液壓或熱力系統，這個算法都會有用武之地。可以這樣說，如果沒有這個算法，現代文明將不復存在。
9 數據壓縮算法
在現今的電子信息技術領域，正發生著一場有長遠影響的數字化革命。由於數字化的多媒體信息尤其是數字視頻、音頻信號的數據量特別龐大，如果不對其進行有效的壓縮就難以得到實際的應用。因此，數據壓縮技術已成為當今數字通信、廣播、存儲和多媒體娛樂中的一項關鍵的共性技術。
10 隨機數生成
在統計學的不同技術中需要使用隨機數，比如在從統計總體中抽取有代表性的樣本的時候，或者在將實驗動物分配到不同的試驗組的過程中，或者在進行蒙特卡羅模擬法計算的時候等等。
閱讀更多 CDA數據分析師 的文章
