36氪 發表於 2014年6月03日 12:00
軟體正在統治世界。而軟體的核心則是演算法。演算法千千萬萬，又有哪些演算法屬於「皇冠上的珍珠」呢？Marcos Otero 給出了他的看法。
什麼是演算法？
通俗而言，演算法是一個定義明確的計算過程，可以一些值或一組值作為輸入並產生一些值或一組值作為輸出。因此演算法就是將輸入轉為輸出的一系列計算步驟。
—Thomas H. Cormen，Chales E. Leiserson，演算法入門第三版
簡而言之，演算法就是可完成特定任務的一系列步驟，它應該具備三大特徵：
- 有限
- 指令明確
- 有效
以下是 Marcos Otero 推薦的十大演算法：
1、合併排序、快速排序及堆排序
最好的排序演算法跟需求密切相關，很難評判。但是從使用上說，這三種的使用頻率更高。
合併排序由馮．諾依曼於 1945 年發明。這是一種基於比較的排序演算法，採用分而治之的辦法解決問題，其階是 O(n^2)。
快速排序可採用原地分割方法，也可採用分而治之演算法。這不是一種穩定的排序演算法，但對於基於 RAM（記憶體）的陣列排序來說非常有效。
堆排序採用優先順序佇列來減少資料中的搜尋時間。該演算法也是原地演算法，並非穩定排序。
這些排序演算法相對於以前的冒泡排序演算法等有了巨大改進，實際上我們今天的資料採擷、人工智慧、連結分析及包括 web 在內的大多數電腦工具都要感謝它們。
2、傅立葉變換與快速傅立葉變換
我們的整個數位世界都使用這兩個簡單但非常強大的演算法，其作用是將訊號從時域轉為頻域或者反之。實際上，你看得到這篇文章得感謝這些演算法。
網際網路、你的 WiFi、智慧型手機、電話、電腦、路由器、衛星，幾乎所有內建有電腦的東西都會以各種方式使用這兩演算法。如果不研究這些演算法，你就拿不到電子、計算或通信方面的學位。
3、迪科斯徹（Dijkstra）演算法
Dijkstra是一種圖譜搜尋演算法。許多問題都可以建模為圖譜，然後利用 Dijkstra 尋找兩個節點之間的最短路徑。如果沒有 Dijkstra 演算法，網際網路的運作效率必將大大降低。雖然今天我們已經有了更好的尋找最短路徑的解決方案，但出於穩定性的要求，Dijkstra 演算法仍然被很多系統使用。
4、RSA加密演算法
如果沒有密碼術和網路安全，網際網路就不會像今天一樣重要，因為電子商務和電子交易需要這些技術來確保交易安全。而RSA演算法是最重要的密碼學演算法之一。該演算法由同名公司的創始人（Ron Rivest、Adi Shamir 和 Leonard Adleman）開發，它讓密碼學普及到了千家萬戶並奠定了密碼術的應用基礎。RSA 要解決的問題既簡單又複雜：如何在獨立平台與最終用戶之間共用公開金鑰。其解決方案是加密。
RSA 加密的基礎是一個十分簡單的數論事實：將兩個大質數相乘十分容易，但是想要對其乘積進行因式分解卻極其困難，因此可以將乘積公開作為加密金鑰。但在分散式運算和量子電腦理論日趨成熟的今天，RSA 加密安全性受到了挑戰。
5、安全雜湊演算法（SHA）
這個實際上並不算是演算法，而是由美國國家標準技術研究所開發的一系列密碼雜湊函數。但是這系列函數是全世界運作的基石。應用程式商店，電子郵件、反病毒、瀏覽器等在使用SHA系列函數，SHA 函數可用來確定下載的東西是否自己想要的東西，還是說遭遇了中間人攻擊或釣魚攻擊。
6、質因數分解
這是一個在電腦領域使用頻繁的數學演算法。如果沒有這一演算法，密碼技術就會變得不安全得多。質因數分解是用來將一個合數分解成一系列質因數的一系列步驟。質因數分解可被視為是 FNP 問題（FNP 是難以解決的典型 NP 問題的擴展）。
許多密碼協定均基於難以分解的大型合數或相關問題。比方說前面提到的 RSA 問題。如果有演算法能夠有效分解任意數位，那麼就會使得基於 RSA 的公開金鑰密碼系統陷入不安全的境地。
而量子電腦的誕生則讓此問題的解決變得容易，從而也打開了一個全新的領域，可利用量子世界的屬性來讓系統更加安全。
7、連結分析
在網路時代，不同實體間關係的分析至關重要。從搜尋引擎和社群網路到行銷分析工具，每個人都想找出網路的真正結構。
連結分析無疑是公眾對演算法的最大困惑與迷思之一。其問題在於進行連結分析有不同的方式，而增加一些特徵就會令每一演算法略有不同（從而使得演算法受到專利保護），但基本上這些演算法都是類似的。
連結分析演算法首先由 Gabriel Pinski 和 Francis Narin 在 1976 年發明。其背後的思路很簡單，即把圖譜以矩陣的形式表示，從而轉為特徵值問題，而特徵值有助於瞭解圖譜結構及每個節點的相對重要性。
Google 的 PageRank，Facebook 展示新聞源，Google+，Facebook 朋友推薦，LinkedIn 工作及連絡人推薦，Netflix 與 Hulu 的電影推薦，YouTube 影片推薦等均使用了連結分析演算法。雖然每個都有不同的目標和參數，但其背後的數學是一樣的。
8、比例積分微分演算法
如果你用過飛機、汽車、衛星服務或手機網路，如果你在工廠待過或者見過機器人，那麼你已經見識過這一PID演算法的作用了。
該演算法利用了控制迴路機制來讓期望輸出訊號與實際輸出訊號之間的錯誤降到最小。只要需要訊號處理或需要電子系統來控制自動化的機械、水力或熱力系統就要用到它。
因此可以說如果沒有這一演算法，人類的現代文明將不復存在。
9、資料壓縮演算法
資料壓縮演算法無疑是非常重要的，因為幾乎在所有的結構中都要用到。除了最明顯的壓縮文件以外，網頁下載時也會壓縮，影片遊戲、影片、音樂、資料存儲、雲端計算、資料庫等等也都要使用壓縮演算法。可以說幾乎所有應用都要使用壓縮演算法。壓縮演算法讓系統更有效成本更低，但是要想確定哪一個最重要卻很困難，因為應用不同，使用的壓縮演算法從 zip 到 mp3、JPEG 或 MPEG-2 各異。
10、亂數產生演算法
很多應用都需要亂數。像 interlink connection，密碼系統、影片遊戲、人工智慧、最佳化、問題的初始條件，金融等都需要生成亂數。但實際上目前我們並沒有「真正」的亂數產生器，儘管有一些偽亂數產生器也是非常有效的。
當然，十大演算法也可能有湊數之嫌，審視的角度不同對演算法的重要性看法也會很不一樣，如果你認為這一榜單有錯漏的地方，不妨在評論中貢獻你的意見。(medium.com)
留言列表
103學年度教學現場紀錄 
