事實上,早在公元前 1600 年就已經出現第一條記錄在案的數學算法——巴比倫人發現了最早的已知算法,用于分解平方根。因此,回到文章開頭我們討論的問題,我讀到的那篇文章將算法視為計算實體,但如果采取這樣一個更為寬泛的定義,那么支配世界的十大算法很可能體現為算術方法(例如減法、乘法等)。
算法究竟是什么?
直白地講,算法是指一切經過明確定義的計算過程,其將某個或者某組值作為輸入內容,并產生某個或者某組值作為輸出結果。因此,算法代表的是一系列計算步驟,用于將輸入轉換為輸出。
更簡單地總結,我們可以將算法視為一系列用于解決某個任務的步驟(是的,不僅僅是計算機會使用算法,人類同樣在使用算法)。就目前的標準來看,算法應當具有以下三大重要特征才被視為擁有實際效果:
應該是有限的: 算法應該在有限的時間內用有限的步驟解決掉其旨在解決的問題,也就是說算法必須在有限的時間內可以完成,要不然就沒有現實意義。
應該具有明確的指令: 算法中的每個步驟必須經過精確定義 ; 同時應針對每種情況做出明確說明。
應該切實有效: 算法應當能夠解決其旨在解決的問題。此外,算法應該被證明可以單純利用紙筆工具實現收斂。
此外,需要強調的是算法的應用不僅局限于計算科學,同時它也作為一種數學實體。但是,如果采取我們在本文中做出的算法定義,那么問題仍然存在:支配世界的十種算法究竟有哪些?在這里,我列出一份小小的清單,排名不分先后。
1. 合并排序,快速排序與堆排序
對元素進行排序的最佳算法是什么?具體答案取決于你的實際需要,因此我把這三種比較常用的排序算法列為同一類 ; 也許你更偏愛其中一種,但事實上三者都非常重要。
其中合并排序算法是迄今為止我們所擁有的最為重要的算法之一。這是一種基于比較的排序算法,以分治的方法解決原本時間復雜度為 O(n^2) 的問題。該算法由數學家 John von Neumann 于 1945 年發明得出。
快速排序是另一種用于解決排序問題的方法,其能夠實現就地分區,同樣屬于一類分而治之的算法。該算法的問題在于其在排序方面并不穩定,但在對基于內存的數組進行排序時表現出色。
最后是堆排序算法,其利用優先級隊列來減少數據中的搜索時間。該算法同樣屬于就地算法,且同樣不屬于穩定排序。
2. 傅利葉變換與快速傅利葉變換
整個數字世界都在使用這些簡單但非常強大的算法,這些算法能夠將信號從時域轉換為頻域,反之亦然。事實上,正是由于這些算法的存在,本篇文章才能被更多朋友所看到。
3. 迪杰斯特拉算法(又譯戴克斯特拉算法)
實事求是地講,如果沒有這種算法,互聯網根本無法像今天這樣保持高效運作。這種圖搜索算法具有多種應用方式,能夠將需要解決的問題建模為圖,并在其中找到兩個節點間的最短路徑。
今天,雖然我們已經擁有更好的最短路徑問題解決方案,但迪杰斯特拉算法仍然在強調穩定性的眾多系統當中得到廣泛應用。
4. RSA 算法
如果沒有加密與網絡安全機制作為保障,互聯網的重要程度不可能達到如今的水平。大家可能會想“胡說,國家安全局局和眾多情報機構的監控早就毀掉了互聯網安全”或者“互聯網根本就沒有安全可言,傻子才會相信這種安全宣傳”; 但必須承認,大多數人仍然具有一定程度的安全信心,否則你根本就不會通過互聯網進行消費。畢竟如果真的否定現有網絡體系的安全性,誰會愿意在 Web 服務中輸入自己的信用卡號碼?
在密碼學領域,有一種算法仍然是目前世界上最重要的算法之一,這就是 RSA 算法。該算法由 RSA 公司的創始人們開發而成,使得密碼學成果得以供世界上的每個人隨意使用,甚至最終塑造了當今密碼學技術的實現方式。RSA 算法希望解決的問題是如何在獨立平臺及最終用戶之間共享公鑰,從而實現加密。
5. 安全哈希算法
這實際上并不是真正的算法,而是由 NIST(美國國家標準技術研究所)所開發的一系列加密散列函數。然而,該算法家族對于世界秩序的維持起到了至關重要的作用。從應用程序商店、電子郵件、防病毒軟件再到常用的網絡瀏覽器,這一切都在使用這類算法用以確定你所下載的是否正是你希望獲得的內容,或者你是否已經成為中間人攻擊或者網絡釣魚攻擊的受害者。
6. 整數分解
這是一種在計算領域被大量采用的數學算法。如果沒有這種算法,密碼學技術的安全水平將受到嚴重破壞。該算法用于將復合數的質數因子分解為較小的非零因數。這也被稱為 FNP 類問題,屬于 NP 類問題的擴展,且解決難度極高。
量子計算的誕生大大降低了此類問題的解決難度,并開辟出一個全新的科學研究領域——利用量子特性保障系統安全。
7. 鏈接分析
在互聯網時代下,分析不同實體間的關系當然非常重要。從搜索引擎到社交網絡再到營銷分析工具,每一方都在努力發現隨著時間推移而不斷變化的互聯網結構。
最后,我想強調一點,雖然很多人認為谷歌公司似乎是第一家使用這種算法的企業,但早在 1996 年(谷歌公司誕生的兩年之前),由 Robin Li 開發的 RankDex 小型搜索引擎已經開始利用這一基本思路進行頁面排名。最終,HyperSearch 的創始人 Massimo Marchiori 也開始使用這種基于單頁間關系的頁面排名算法。(谷歌在其申請的專利當中提到了這兩位奠基者。)
8. 比例微積分算法
大家應該都體驗過飛機、汽車、衛星服務或者手機網絡吧?有些朋友還在工廠當中看到過機器人設備。如果是這樣,那么你已經見識到了這一算法的威力。
9. 數據壓縮算法
很難確定哪種壓縮算法的重要性最高,因為根據實際應用需求,大家使用的算法可能包括 zip、mp3 乃至 JPEG 以及 MPEG-2 等等。但相信大家都能清晰地感受到這些算法在各類結構中的重要作用。
除了最直觀的文件壓縮之外,大家還能在哪里看到壓縮算法的蹤影?很明顯,網頁會利用數據壓縮技術控制你需要下載的文件體積,此外視頻游戲、視頻、音樂、數據存儲、云計算以及數據庫等也都是數據壓縮算法大顯身手的舞臺。可以說,萬事萬物都離不開數據壓縮,這類算法的存在使得系統能夠以成本更低且效率更高的方式為用戶服務。
10. 隨機數生成算法
今天,我們還沒有“真正的”隨機數生成器,但已經擁有眾多完全可以滿足需求的偽隨機數生成器。這些算法廣泛存在于互連鏈接、加密、安全哈希算法、視頻游戲、人工智能、優化、問題條件初始化以及財務等領域。
-
算法
+關注
關注
23文章
4599瀏覽量
92643 -
哈希算法
+關注
關注
1文章
56瀏覽量
10734
原文標題:真正支配整個世界的十種算法
文章出處:【微信號:IV_Technology,微信公眾號:智車科技】歡迎添加關注!文章轉載請注明出處。
發布評論請先 登錄
相關推薦
評論