《TO》導讀：原文來自 Medium，原文作者為 Marcos Otero 曾撰寫過若干技術相關文章。本文以第一人稱編譯。
那天，我正在瀏覽 Reddit 的時候，我看到了一篇叫做「10 個改變世界的演算法」的文章。作者 George Dvorsky 試圖透過文章表達演算法的在這個世界上極大的貢獻，以及介紹那些對我們人類的文明有著最大的影響的演算法。
但是如過你有對演算法略有涉略，你可能會邊讀邊想「這個作者真的知道演算法是什麼嗎？」或是「臉書的動態時報也算是一個演算法？」， 因為如果連那個都算是一種演算法的話，那幾乎所有東西都可以被歸類於演算法下面。因此，我在這篇文章中將會介紹演算法到底是什麼以及 10 個真正改變世界的演算法。
- 什麼是演算法？
簡單的說，演算法是一種將一些「輸入值」經過一些運算後產生出「輸出值」的運算方法。所以演算法其實是將輸入值傳變成輸出值的過程。
其實，我們可以說演算法就只是完成某項任務的步驟（並不是只有電腦在使用演算，人們也在用）。一個有效的演算法有三個必要的條件:
1. 它必須要是有限的。如果你的演算法在解決問題以後還在跑，那它便不是一個有效的演算法。
2. 它的每一個步驟都要被清楚的規範。演算法的每一個步驟都要非常的精確，那些指示應該在每個情況下都有非常明確的規範。
3. 它要是用的。那個演算法必須要解決那個問題，並且應該可以要用紙筆就可以證明他是可以解決你的問題。
但是很重要的是，演算法並不是僅僅用於電腦科學上，他在數學上也有極大的用處。事實上，人類史上第一個有 紀載的數學演算法是西元前 1600 年前巴比倫人用來計算平方根的 。所以 George Dvorsky 在他那篇文章的問題其實是他把演算法侷限在電腦上的應用，而當你把用演算法真正的定義的話，你會在有關數學的書裡找到十個影響最大的演算法（加減乘除之類的）。
但是即便我們只考慮在電腦上應用的演算法，問題仍然存在：到底是哪十個演算法對世界最有影響？我在下面整理了十個改變世界的演算法，但是他們的順序並不代表影響力的大小。
- 合併排序法、快速排序法 還有堆積排序法
哪一個最好的排序的演算法呢？其實這三個演算法的優劣完全看你的需要，所以在這裡我才把三種方法都列出來。你個人可能有偏好其中一種，但是這三個演算法都同樣的重要。
由數學家 John von Neumann 在 1945 年所發明的 合併排序法（Merge Sort）是截至目前為止最重要的演算法之一，因為透過將一個大的問題分解成極多的小的問題，他把一個需要大 n 平方時間的任務變成了 nlog(n) 。
雖然同樣都是將一個大問題化成許多小問題， 快速排序法（Quick Sort）不同於 Merge Sort 的是， 他是不斷的透過支點將資料排序。雖然 Quick Sort 並不是一個穩定的排序演算法，但是他是一個處理 RAM（隨機處理記憶體）極有效率的演算法。
最後， 堆積排序法（Heap Sort）是使用優先序列來降低搜尋資料的時間。這個演算法跟 Quick Sort 一樣都不穩定並且也都是 in-place 演算法。
這些演算法大大的改進了先前的 氣泡排序法 ，並且因為有這些演算法，我們現在才可以有像是 Data mining， 人工智慧，連結分析，以及網路等電腦上的應用。
- 傅立葉變換 以及快速傅立葉變換
我們所有跟數位傳輸有關的東西都是透過 傅立葉變換（Fourier Transform）。他將訊號的時間領域轉變為頻率，反之亦然。
網路、無線網路、智慧型手機、一般電話、電腦、路由器、衛星和幾乎任何跟電腦有關的東西都在某種程度上使用到他。
事實上是，你們要看到這篇文章也是有賴於這個演算法。如果你想要研究電子產品，電腦或是通訊傳播的話，你一定會要學到這個無比重要的演算法。
-
戴克斯特拉演算法
（圖片來源：wikipedia；由 Goran tek-en 上傳）
「要是沒有這個演算法，我們的網路便不會運作得如此迅速」，這句話套用在 Dijkstra 演算法 上並不為過。這個在圖像搜尋的演算法的運用十分廣泛，包括找尋兩點之間的最短路徑。
即便今天我們有更好的演算法可以找出兩點間的最短路徑， 在需要穩定性的系統哩，我們仍然在繼續地在使用 Dijkstra 演算法。
- RSA 加密演算法
如果沒有網路安全和密碼學，現在的網路便不會如此的重要。你可能會覺得網路安全是 NSA 或是其他情報機關的事，跟你自己毫不相干，或是，只有那些天真的人才會覺得網路上的資料是安全的。
但是，人們要感到自己的資料在網路上是安全的才會在網路上消費，沒有我們前面說的資安保護，人們便不會在網路上輸入自己的信用卡卡號來網購。
此外，從密碼學的角度來說，由 RSA 公司開發出的 RSA 演算法 是史上最重要的演算法之一。這個演算法不但讓每個人都可以使用密碼學，更改變了現在人們使用密碼學的習慣。RSA 演算法解決了一個一個既簡單又複雜的問題：要怎樣在各自獨立的平台和終端使用者之間分享資訊，同時透過鎖碼讓資訊不外流？（我個人認為這個問題並還沒有被解決，需要更多的心血花在解決這個問題上。）
- 安全雜湊演算法（Secure Hash Algorithm）
與其說這是一個單獨的演算法，這比較像許多由美國的 NIST 所開發出的鎖碼的方法。
這些演算法 是許多像是應用程式商店、電子郵件、防毒軟體、瀏覽器的基石，因為他們都是透過這些演算法（事實上是那些鎖碼的方法）來確認你下載的東西是你要的而不是某個惡意程式，讓你免時遭受釣魚攻擊。
- 整數分解（Integer Factorization）
這項演算法應用十分廣泛，若缺少了這項演算法，加密技術的安全性將大大降低。這項演算法主要是一連串用於用於進行質因數分解的程序。由於這通常被視為 FNP 問題，屬於 NP 等級的延伸，從而大大增加了問題的難度。
許多加密方法的基礎都建立在質因數分解或 RSA 問題等相關問題之上。一個可以有效分析出隨機因數的演算法，將嚴重危及以 RDA 為基礎的加密法。量子演算的發明，大大降低了解決這項問題的難度，開啟了一個全新以量子性質作為加密基礎的方式。
- 鏈結分析（Link Analysis）
（圖片來源：Marc_Smith，CC Licensed）
在網路時代，不同使用者間連結的的分析十分重要。
搜尋引擎、社群網站到行銷分析等機構，都正試圖找出網路的的結構。對一般大眾而言，連結分析可說是撲朔迷離且令人費解的。不過，儘管每種連結分析的演算法都有些許不同，但其實大多都建立在相同的基礎之上。
連結分析的基本想法非常簡單，透過將表格化為方陣的方式，即可將問題簡化為特徵值（eigenvalue）的計算。而特徵值將反映資料的結構與每一項組成元素之間的關係。這項演算方式是由 Gabriel Pinski and Francis Narin 在 1976 年所發展的。
這項演算法已經被普遍的運用在一般的日常生活中，如 Google 的 Paper Rank、Facebook 的 news feed、Google+ 與 Facebook 的可能好友、LinkedIn 的工作推薦、Netflix、Hulu、Youtube 的、影片推薦等。
最後，雖然 Google 看起來好像是第一家將連結分析投入市場應用的公司，但其實在 1996 年（Google 成立的兩年前），一家由 Robin Li 所創立名為 RankDex 的搜尋引擎早已將連結分析用於搜尋結果的優先排序上了。另外，HyperSearch 的創辦人 Massimo Marchiori 也早已將連結分析應用於網頁關聯的分析上了。
- 比例積分微分演算法（Proportional Integral Derivative Algorithm）
（圖片來源：wikipedia；由 TravTigerEE 上傳）
任何使用過飛機、汽車、衛星服務、手機網路或參觀過工廠製造過程的人，都已經親眼見過這項演算法的威力了。
基本上，這項演算法利用迴圈反饋機制，將理想結果與實際結果間的誤差最小化。這項演算法已經被廣泛應用在所有電子控制系統之中。也就是說，如果沒有這項演算法，一般人所知的現代文明將不可能存在。
- 資料壓縮演算法（Data compression algorithms）
由於隨著壓縮標的不同，所需的演算法也略有不同，要決定哪一個演算法的重要性最高是件困難的挑戰。但眾所皆知的是，這些演算法的重要性不容置疑。
除了 zip 文件以外，不論是從網頁上、遊戲中、雲端所下載的任何形式資料，都需要經過壓縮程序。可以說，透過壓縮程序，整個網路傳輸的成本才能大大降低致人人可負擔得起。（可參考維基百科 。）
- 隨機亂數產生器（Random Number Generation）
雖然到目前為止，完全隨機的數字產生演算法尚未出現，一些接近隨機的數字產生演算法已經十分有效了。這些演算法被用於許多應用，包含連結建立、加密技術、AI，甚至是遊戲之中。
這項排名只是我的個人見解，而非具有公信力的排名。
（資料來源：《medium.com》）
留言列表
