Search
Close this search box.

個人意見:這十個演算法,才是真的改變世界的重量級演算法

《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)

1*2OvavWCXN7UvDrh21zU5nw

 

(圖片來源:wikipedia;由TravTigerEE 上傳)

任何使用過飛機、汽車、衛星服務、手機網路或參觀過工廠製造過程的人,都已經親眼見過這項演算法的威力了。

基本上,這項演算法利用迴圈反饋機制,將理想結果與實際結果間的誤差最小化。這項演算法已經被廣泛應用在所有電子控制系統之中。也就是說,如果沒有這項演算法,一般人所知的現代文明將不可能存在。

  • 資料壓縮演算法(Data compression algorithms)

由於隨著壓縮標的不同,所需的演算法也略有不同,要決定哪一個演算法的重要性最高是件困難的挑戰。但眾所皆知的是,這些演算法的重要性不容置疑。

除了 zip 文件以外,不論是從網頁上、遊戲中、雲端所下載的任何形式資料,都需要經過壓縮程序。可以說,透過壓縮程序,整個網路傳輸的成本才能大大降低致人人可負擔得起。(可參考維基百科。)

  • 隨機亂數產生器(Random Number Generation)

雖然到目前為止,完全隨機的數字產生演算法尚未出現,一些接近隨機的數字產生演算法已經十分有效了。這些演算法被用於許多應用,包含連結建立、加密技術、AI,甚至是遊戲之中。

這項排名只是我的個人見解,而非具有公信力的排名。

(資料來源:《medium.com》)