學(xué)號(hào)：16069130022 ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?姓名：李鳳儀
鏈接：
【嵌牛導(dǎo)讀】主宰全球的10大算法
【嵌牛鼻子】算法
【嵌牛提問】
【嵌牛正文】
【編者按】Reddit有篇帖子介紹了算法對(duì)我們現(xiàn)在生活的重要性鸽斟，以及哪些算法對(duì)現(xiàn)代文明所做貢獻(xiàn)最大冕房。這個(gè)表單并不完整纸兔，很多與我們密切相關(guān)的算法都沒有提到俩块，如機(jī)器學(xué)習(xí)和矩陣乘法授药，歡迎你繼續(xù)補(bǔ)充荆秦。
如果對(duì)算法有所了解背捌，讀這篇文章時(shí)你可能會(huì)問“作者知道算法為何物嗎戳粒？”路狮，或是“Facebook的‘信息流’(News Feed)算是一種算法嗎？”蔚约，如果“信息流”是算法奄妨，那就可以把所有事物都?xì)w結(jié)為一種算法。才疏學(xué)淺苹祟，結(jié)合那篇帖子砸抛，接下來我試著解釋一下算法是什么评雌，又是哪些算法正在主導(dǎo)我們的世界。
什么是算法直焙？
簡而言之景东，任何定義明確的計(jì)算步驟都可稱為算法，接受一個(gè)或一組值為輸入奔誓，輸出一個(gè)或一組值斤吐。(來源：homas H. Cormen, Chales E. Leiserson 《算法導(dǎo)論第3版》)
可以這樣理解，算法是用來解決特定問題的一系列步驟（不僅計(jì)算機(jī)需要算法丝里，我們?cè)谌粘Ｉ钪幸苍谑褂盟惴ǎ┣酢Ｋ惴ū仨毦邆淙缦?個(gè)重要特性：
有窮性，執(zhí)行有限步驟后杯聚，算法必須中止臼婆。
確切性，算法的每個(gè)步驟都必須確切定義幌绍。
可行性颁褂，特定算法須可以在特定的時(shí)間內(nèi)解決特定問題，
其實(shí)傀广，算法雖然廣泛應(yīng)用在計(jì)算機(jī)領(lǐng)域颁独，但卻完全源自數(shù)學(xué)。實(shí)際上伪冰，最早的數(shù)學(xué)算法可追溯到公元前1600年-Babylonians有關(guān)求因式分解和平方根的算法誓酒。
那么又是哪10個(gè)計(jì)算機(jī)算法造就了我們今天的生活呢？請(qǐng)看下面的表單贮聂，排名不分先后：
1歸并排序(MERGE SORT)靠柑、快速排序(QUICK SORT)和堆積排序(HEAP SORT)
哪個(gè)排序算法效率最高？這要看情況吓懈。這也就是我把3種算法放在一起講的原因歼冰，可能你更常用其中一種，不過它們各有千秋耻警。
歸并排序算法隔嫡，是目前為止最重要的算法之一，是分治法的一個(gè)典型應(yīng)用甘穿，由數(shù)學(xué)家John von Neumann于1945年發(fā)明腮恩。
快速排序算法，結(jié)合了集合劃分算法和分治算法扒磁，不是很穩(wěn)定庆揪，但在處理隨機(jī)列陣(AM-based arrays)時(shí)效率相當(dāng)高。
堆積排序妨托，采用優(yōu)先佇列機(jī)制缸榛，減少排序時(shí)的搜索時(shí)間，同樣不是很穩(wěn)定兰伤。
與早期的排序算法相比(如冒泡算法)内颗，這些算法將排序算法提上了一個(gè)大臺(tái)階。也多虧了這些算法敦腔，才有今天的數(shù)據(jù)發(fā)掘均澳，人工智能，鏈接分析符衔，以及大部分網(wǎng)頁計(jì)算工具找前。
2傅立葉變換和快速傅立葉變換
這兩種算法簡單，但卻相當(dāng)強(qiáng)大判族，整個(gè)數(shù)字世界都離不開它們躺盛，其功能是實(shí)現(xiàn)時(shí)間域函數(shù)與頻率域函數(shù)之間的相互轉(zhuǎn)化。能看到這篇文章形帮，也是托這些算法的福槽惫。
因特網(wǎng)，WIFI辩撑，智能機(jī)界斜，座機(jī)，電腦合冀，路由器各薇，衛(wèi)星等幾乎所有與計(jì)算機(jī)相關(guān)的設(shè)備都或多或少與它們有關(guān)。不會(huì)這兩種算法君躺，你根本不可能拿到電子峭判，計(jì)算機(jī)或者通信工程學(xué)位。(USA)
3迪杰斯特拉算法 (Dijkstra’s algorithm)
可以這樣說晰洒，如果沒有這種算法朝抖，因特網(wǎng)肯定沒有現(xiàn)在的高效率。只要能以“圖”模型表示的問題谍珊，都能用這個(gè)算法找到“圖”中兩個(gè)節(jié)點(diǎn)間的最短距離治宣。
雖然如今有很多更好的方法來解決最短路徑問題，但代克思托演算法的穩(wěn)定性仍無法取代砌滞。
4RSA非對(duì)稱加密算法
毫不夸張地說侮邀，如果沒有這個(gè)算法對(duì)密鑰學(xué)和網(wǎng)絡(luò)安全的貢獻(xiàn)，如今因特網(wǎng)的地位可能就不會(huì)如此之高”慈螅現(xiàn)在的網(wǎng)絡(luò)毫無安全感绊茧，但遇到錢相關(guān)的問題時(shí)我們必需要保證有足夠的安全感，如果你覺得網(wǎng)絡(luò)不安全打掘，肯定不會(huì)傻乎乎地在網(wǎng)頁上輸入自己的銀行卡信息华畏。
RSA算法鹏秋，密鑰學(xué)領(lǐng)域最牛叉的算法之一，由RSA公司的三位創(chuàng)始人提出亡笑，奠定了當(dāng)今的密鑰研究領(lǐng)域侣夷。用這個(gè)算法解決的問題簡單又復(fù)雜：保證安全的情況下，如何在獨(dú)立平臺(tái)和用戶之間分享密鑰仑乌。
5哈希安全算法(Secure Hash Algorithm)
確切地說百拓，這不是一種算法，而是一組加密哈希函數(shù)晰甚，由美國國家標(biāo)準(zhǔn)技術(shù)研究所首先提出衙传。無論是你的應(yīng)用商店，電子郵件和殺毒軟件厕九，還是瀏覽器等等蓖捶，都使用這種算法來保證你正常下載，以及是否被“中間人攻擊”止剖，或者“網(wǎng)絡(luò)釣魚”腺阳。
6整數(shù)質(zhì)因子分解算法(Integer factorization)
這其實(shí)是一個(gè)數(shù)學(xué)算法，不過已經(jīng)廣泛應(yīng)用與計(jì)算機(jī)領(lǐng)域穿香。如果沒有這個(gè)算法亭引，加密信息也不會(huì)如此安全。通過一系列步驟將皮获，它可以將一個(gè)合成數(shù)分解成不可再分的數(shù)因子焙蚓。
很多加密協(xié)議都采用了這個(gè)算法，就比如剛提到的RSA算法洒宝。
7鏈接分析算法(Link Analysis)
在因特網(wǎng)時(shí)代购公，不同入口間關(guān)系的分析至關(guān)重要。從搜索引擎和社交網(wǎng)站雁歌，到市場分析工具宏浩，都在不遺余力地尋找因特網(wǎng)的正真構(gòu)造。
鏈接分析算法一直是這個(gè)領(lǐng)域最讓人費(fèi)解的算法之一靠瞎，實(shí)現(xiàn)方式不一比庄，而且其本身的特性讓每個(gè)實(shí)現(xiàn)方式的算法發(fā)生異化，不過基本原理卻很相似乏盐。
鏈接分析算法的機(jī)制其實(shí)很簡單：你可以用矩陣表示一幅“圖“佳窑，形成本征值問題。本征值問題可以幫助你分析這個(gè)“圖”的結(jié)構(gòu)父能，以及每個(gè)節(jié)點(diǎn)的權(quán)重神凑。這個(gè)算法于1976年由Gabriel Pinski和Francis Narin提出。
誰會(huì)用這個(gè)算法呢何吝？Google的網(wǎng)頁排名溉委，F(xiàn)acebook向你發(fā)送信息流時(shí)(所以信息流不是算法鹃唯，而是算法的結(jié)果)，Google+和Facebook的好友推薦功能薛躬，LinkedIn的工作推薦俯渤，Youtube的視頻推薦呆细，等等型宝。
普 遍認(rèn)為Google是首先使用這類算法的機(jī)構(gòu)，不過其實(shí)早在1996年(Google 問世2年前)李彥宏就創(chuàng)建的“RankDex”小型搜索引擎就使用了這個(gè)思路絮爷。而Hyper Search搜索算法建立者馬西莫·馬奇奧里也曾使用過類似的算法趴酣。這兩個(gè)人都后來都成為了Google歷史上的傳奇人物。
8比例微積分算法(Proportional Integral Derivative Algorithm)
飛機(jī)坑夯，汽車岖寞，電視，手機(jī)柜蜈，衛(wèi)星仗谆，工廠和機(jī)器人等等事物中都有這個(gè)算法的身影。
簡單來講淑履，這個(gè)算法主要是通過“控制回路反饋機(jī)制”隶垮，減小預(yù)設(shè)輸出信號(hào)與真實(shí)輸出信號(hào)間的誤差。只要需要信號(hào)處理秘噪，或電子系統(tǒng)來控制自動(dòng)化機(jī)械狸吞，液壓和加熱系統(tǒng)，都需要用到這個(gè)算個(gè)法指煎。
沒有它蹋偏，就沒有現(xiàn)代文明。
9數(shù)據(jù)壓縮算法
數(shù)據(jù)壓縮算法有很多種至壤，哪種最好威始？這要取決于應(yīng)用方向，壓縮mp3像街，JPEG和MPEG-2文件都不一樣黎棠。
哪里能見到它們？不僅僅是文件夾中的壓縮文件宅广。你正在看的這個(gè)網(wǎng)頁就是使用數(shù)據(jù)壓縮算法將信息下載到你的電腦上葫掉。除文字外，游戲跟狱，視頻俭厚，音樂，數(shù)據(jù)儲(chǔ)存驶臊，云計(jì)算等等都是挪挤。它讓各種系統(tǒng)更輕松叼丑，效率更高。
10隨機(jī)數(shù)生成算法
到如今扛门，計(jì)算機(jī)還沒有辦法生成“正真的”隨機(jī)數(shù)鸠信，但偽隨機(jī)數(shù)生成算法就足夠了。這些算法在許多領(lǐng)域都有應(yīng)用论寨，如網(wǎng)絡(luò)連接星立，加密技術(shù)，安全哈希算法葬凳，網(wǎng)絡(luò)游戲绰垂，人工智能，以及問題分析中的條件初始化火焰。
