統(tǒng)治世界的 10 大算法，你知道幾個(gè)？

點(diǎn)擊上方“小白學(xué)視覺(jué)”，選擇加"星標(biāo)"或“置頂”

重磅干貨，第一時(shí)間送達(dá)

   

    

     

      本文轉(zhuǎn)自|視覺(jué)算法
     
    
   
   

    
   


   

    
   
   

    一篇有趣的文章《統(tǒng)治世界的十大算法》中，作者George Dvorsky試圖解釋算法之于當(dāng)今世界的重要性，以及哪些算法對(duì)人類(lèi)文明最為重要。
   
   

    

   
   

    

     

      
 1 排序算法  
     
    
   


   

    所謂排序，就是使一串記錄，按照其中的某個(gè)或某些關(guān)鍵字的大小，遞增或遞減的排列起來(lái)的操作。排序算法，就是如何使得記錄按照要求排列的方法。排序算法在很多領(lǐng)域得到相當(dāng)?shù)刂匾暎绕涫窃诖罅繑?shù)據(jù)的處理方面。一個(gè)優(yōu)秀的算法可以節(jié)省大量的資源。
   
   

    

   
   

    
   


   

    穩(wěn)定的
   
   

    
冒泡排序（bubble sort） — O(n^2）
    
雞尾酒排序(Cocktail sort，雙向的冒泡排序) — O(n^2）
    
插入排序（insertion sort）— O(n^2)
    
桶排序（bucket sort）— O(n); 需要 O(k) 額外空間
    
計(jì)數(shù)排序(counting sort) — O(n+k); 需要 O(n+k) 額外空間
    
合并排序（merge sort）— O(nlog n);需要 O(n) 額外空間
    
原地合并排序— O(n^2)
    
二叉排序樹(shù)排序 （Binary tree sort） — O(nlog n)期望時(shí)間；O(n^2)最壞時(shí)間；需要 O(n) 額外空間
    
鴿巢排序(Pigeonhole sort)— O(n+k); 需要 O(k) 額外空間
    
基數(shù)排序（radix sort）— O(n·k); 需要 O(n) 額外空間
    
Gnome 排序— O(n^2)
    
圖書(shū)館排序— O(nlog n) withhigh probability，需要（1+ε)n額外空間
   


   

    不穩(wěn)定的
   
   

    
選擇排序（selection sort）— O(n^2)
    
希爾排序（shell sort）— O(nlog n) 如果使用最佳的現(xiàn)在版本
    
組合排序— O(nlog n)
    
堆排序（heapsort）— O(nlog n)
    
平滑排序— O(nlog n)
    
快速排序（quicksort）— O(nlog n) 期望時(shí)間，O(n^2) 最壞情況；對(duì)于大的、亂數(shù)列表一般相信是最快的已知排序
    
Introsort—O(nlog n)
    
Patience sorting— O(nlog n+k) 最壞情況時(shí)間，需要額外的 O(n+ k) 空間，也需要找到最長(zhǎng)的遞增子串行（longest increasing subsequence）
   


   

    不實(shí)用的
   
   

    
Bogo排序— O(n× n!) 期望時(shí)間，無(wú)窮的最壞情況。
    
Stupid sort— O(n^3); 遞歸版本需要 O(n^2)額外存儲(chǔ)器
    
珠排序（Bead sort） — O(n) or O（√n)，但需要特別的硬件
    
Pancake sorting— O(n)，但需要特別的硬件
    
stooge sort——O（n^2.7）很漂亮但是很耗時(shí)
   
   

    

   
   

    

     

      
 2 傅立葉變換與快速傅立葉變換  
     
    
   


   

    傅立葉是一位法國(guó)數(shù)學(xué)家和物理學(xué)家，原名是JeanBaptiste Joseph Fourier(1768-1830), Fourier于1807年在法國(guó)科學(xué)學(xué)會(huì)上發(fā)表了一篇論文，論文里描述運(yùn)用正弦曲線(xiàn)來(lái)描述溫度分布，論文里有個(gè)在當(dāng)時(shí)具有爭(zhēng)議性的決斷：任何連續(xù)周期信號(hào)都可以由一組適當(dāng)?shù)恼仪€(xiàn)組合而成。
   
   

    當(dāng)時(shí)審查這個(gè)論文拉格朗日?qǐng)?jiān)決反對(duì)此論文的發(fā)表，而后在近50年的時(shí)間里，拉格朗日?qǐng)?jiān)持認(rèn)為傅立葉的方法無(wú)法表示帶有棱角的信號(hào)，如在方波中出現(xiàn)非連續(xù)變化斜率。直到拉格朗日死后15年這個(gè)論文才被發(fā)表出來(lái)。
   
   

    誰(shuí)是對(duì)的呢？拉格朗日是對(duì)的：正弦曲線(xiàn)無(wú)法組合成一個(gè)帶有棱角的信號(hào)。但是，我們可以用正弦曲線(xiàn)來(lái)非常逼近地表示它，逼近到兩種表示方法不存在能量差別，基于此，傅立葉是對(duì)的。
   
   

    為什么我們要用正弦曲線(xiàn)來(lái)代替原來(lái)的曲線(xiàn)呢？如我們也還可以用方波或三角波來(lái)代替呀，分解信號(hào)的方法是無(wú)窮多的，但分解信號(hào)的目的是為了更加簡(jiǎn)單地處理原來(lái)的信號(hào)。
   
   

    用正余弦來(lái)表示原信號(hào)會(huì)更加簡(jiǎn)單，因?yàn)檎嘞覔碛性盘?hào)所不具有的性質(zhì)：正弦曲線(xiàn)保真度。一個(gè)正余弦曲線(xiàn)信號(hào)輸入后，輸出的仍是正余弦曲線(xiàn)，只有幅度和相位可能發(fā)生變化，但是頻率和波的形狀仍是一樣的。且只有正余弦曲線(xiàn)才擁有這樣的性質(zhì)，正因如此我們才不用方波或三角波來(lái)表示。
   


   

    

     

      
 3 Dijkstra 算法  
     
    
   


   

    Dijkstra算法是典型的算法。Dijkstra算法是很有代表性的算法。Dijkstra一般的表述通常有兩種方式，一種用永久和臨時(shí)標(biāo)號(hào)方式，一種是用OPEN, CLOSE表的方式，這里均采用永久和臨時(shí)標(biāo)號(hào)的方式。注意該算法要求圖中不存在負(fù)權(quán)邊。
   



   

    

     

      
 4 RSA算法變換  
     
    
   


   

    RSA是目前最有影響力的公鑰加密算法，它能夠抵抗到目前為止已知的絕大多數(shù)密碼攻擊，已被ISO推薦為公鑰數(shù)據(jù)加密標(biāo)準(zhǔn)。
   
   

    今天只有短的RSA鑰匙才可能被強(qiáng)力方式解破。到2008年為止，世界上還沒(méi)有任何可靠的攻擊RSA算法的方式。只要其鑰匙的長(zhǎng)度足夠長(zhǎng)，用RSA加密的信息實(shí)際上是不能被解破的。但在分布式計(jì)算和量子計(jì)算機(jī)理論日趨成熟的今天，RSA加密安全性受到了挑戰(zhàn)。
   
   

    

   
   

    

     

      
 5 安全哈希算法  
     
    
   


   

    一種對(duì)輸入信息（例如消息）進(jìn)行摘要的算法。摘要過(guò)程能夠完成下列特點(diǎn)：不同的輸入信息絕對(duì)不會(huì)具有相同的指紋：相近輸入信息經(jīng)過(guò)摘要之后的輸出信息具有較大的差異，同時(shí)計(jì)算上很難生產(chǎn)一個(gè)與給定輸入具有相同指紋的輸入。（即不可逆）。
   


   

    

     

      
 6 整數(shù)因式分解  
     
    
   


   

    這是在計(jì)算機(jī)領(lǐng)域被大量使用的數(shù)學(xué)算法，沒(méi)有這個(gè)算法，信息加密會(huì)更不安全。該算法定義了一系列步驟，得到將一合數(shù)分解為更小因子的質(zhì)數(shù)分解式。這被認(rèn)為是一種FNP問(wèn)題，它是NP分類(lèi)問(wèn)題的延伸，極其難以解決。
   
   

    許多加密協(xié)議（如RSA算法）都基于這樣一個(gè)原理：對(duì)大的合數(shù)作因式分解是非常困難的。如果一個(gè)算法能夠快速地對(duì)任意整數(shù)進(jìn)行因式分解，RSA的公鑰加密體系就會(huì)失去其安全性。
   
   

    量子計(jì)算的誕生使我們能夠更容易地解決這類(lèi)問(wèn)題，同時(shí)它也打開(kāi)了一個(gè)全新的領(lǐng)域，使得我們能夠利用量子世界中的特性來(lái)保證系統(tǒng)安全。
   


   

    

     

      
 7 鏈接分析  
     
    
   
   

    

   
   

    鏈接分析，源于對(duì)Web結(jié)構(gòu)中超鏈接的多維分析。當(dāng)前其應(yīng)用主要體現(xiàn)在網(wǎng)絡(luò)信息檢索、網(wǎng)絡(luò)計(jì)量學(xué)、數(shù)據(jù)挖掘、Web結(jié)構(gòu)建模等方山。作為Google的核心技術(shù)之一，鏈接分析算法應(yīng)用已經(jīng)顯現(xiàn)出j驚人的商業(yè)價(jià)值。
   


   

    

     

      
 8 比例積分微分算法  
     
    
   


   

    你是否曾經(jīng)用過(guò)飛機(jī)、汽車(chē)、衛(wèi)星服務(wù)或手機(jī)網(wǎng)絡(luò)？你是否曾經(jīng)在工廠(chǎng)工作或是看見(jiàn)過(guò)機(jī)器人？如果回答是肯定的，那么你應(yīng)該已經(jīng)見(jiàn)識(shí)過(guò)這個(gè)算法了。
   
   

    大體上，這個(gè)算法使用一種控制回路反饋機(jī)制，將期望輸出信號(hào)和實(shí)際輸出信號(hào)之間的錯(cuò)誤最小化。無(wú)論何處，只要你需要進(jìn)行信號(hào)處理，或者你需要一套電子系統(tǒng)，用來(lái)自動(dòng)化控制機(jī)械、液壓或熱力系統(tǒng)，這個(gè)算法都會(huì)有用武之地。
   
   

    可以這樣說(shuō)，如果沒(méi)有這個(gè)算法，現(xiàn)代文明將不復(fù)存在。
   


   

    

     

      
 9 數(shù)據(jù)壓縮算法  
     
    
   


   

    在現(xiàn)今的電子信息技術(shù)領(lǐng)域，正發(fā)生著一場(chǎng)有長(zhǎng)遠(yuǎn)影響的數(shù)字化革命。由于數(shù)字化的多媒體信息尤其是數(shù)字視頻、音頻信號(hào)的數(shù)據(jù)量特別龐大，如果不對(duì)其進(jìn)行有效的壓縮就難以得到實(shí)際的應(yīng)用。因此，數(shù)據(jù)壓縮技術(shù)已成為當(dāng)今數(shù)字通信、廣播、存儲(chǔ)和多媒體娛樂(lè)中的一項(xiàng)關(guān)鍵的共性技術(shù)。
   


   

    

     

      
 10 隨機(jī)數(shù)生成  
     
    
   


   

    在統(tǒng)計(jì)學(xué)的不同技術(shù)中需要使用隨機(jī)數(shù)，比如在從統(tǒng)計(jì)總體中抽取有代表性的樣本的時(shí)候，或者在將實(shí)驗(yàn)動(dòng)物分配到不同的試驗(yàn)組的過(guò)程中，或者在進(jìn)行蒙特卡羅模擬法計(jì)算的時(shí)候等等。
   
   

    

   
   

    

   
   

    

     - END -
    
   

交流群

歡迎加入公眾號(hào)讀者群一起和同行交流，目前有SLAM、三維視覺(jué)、傳感器、自動(dòng)駕駛、計(jì)算攝影、檢測(cè)、分割、識(shí)別、醫(yī)學(xué)影像、GAN、算法競(jìng)賽等微信群（以后會(huì)逐漸細(xì)分），請(qǐng)掃描下面微信號(hào)加群，備注：”昵稱(chēng)+學(xué)校/公司+研究方向“，例如：”張三 + 上海交大 + 視覺(jué)SLAM“。請(qǐng)按照格式備注，否則不予通過(guò)。添加成功后會(huì)根據(jù)研究方向邀請(qǐng)進(jìn)入相關(guān)微信群。請(qǐng)勿在群內(nèi)發(fā)送廣告，否則會(huì)請(qǐng)出群，謝謝理解~