博雯 發自 凹非寺  量子位 報道 | 公眾號 QbitAI

軟體演算法對計算速度的提升有多大？

MIT 最新研究說：超過4成演算法對效能的改進，已經超過了硬體的 摩爾定律 。

對於中等規模的問題，30%-43%的演算法的改進比硬體進步更能提升效能。  當問題資料增加到數億規模時，演算法改進變得比硬體改進/摩爾定律更重要。

這就是MIT的兩位科學家對來自57本教科書，超過1137篇研究論文的資料進行分析後得到的結論。

不僅如此，他們還全面敘述了現有以及歷史上的 演算法 何時被發現、如何改進、以及改進的規模。

14%的演算法改進率超過1000%

研究者透過分析 QS 排名中前20的計算機名校所用的課件，總結出11個演算法子領域：

組合學、統計學/機器學習、密碼學、數值分析、資料庫、作業系統、計算機網路、機器人學、訊號處理、計算機圖形/影象處理、生物資訊學。

透過分析子領域中的演算法教材、學術期刊、已發表論文等資訊，研究者劃分出了113個演算法家族，平均每個家族8個演算法。

他們首先統計了從1940年到現在，各種演算法的最初提出時間：

並且根據這些演算法最初被提出時的時間複雜度進行了歸納。可以看到，其中31%的演算法屬於指數複雜度類別：

在時間複雜度的改進上，對於n=100萬的問題規模，一些演算法比硬體或摩爾定律的改進率更高：

演算法改進對四個演算法家族的影響

將這一分析拓展到110個演算法家族上時，可以看到，對於中等規模（n=1000）的問題來說，只有18%的演算法改進率快於硬體。

但當問題規模來到了百萬、億、甚至萬億級別時，演算法的改進速度就超過了硬體效能。

甚至有14%的演算法家族的改進率超過1000%，遠超硬體改進所帶來的效能提升。

a：n=一千 b：n=一百萬 c：n=一億

作者介紹

論文一作Yash Sherry本科畢業於 印度德里大學 計算機科學專業，現在是MIT斯隆商學院的一位研究員，工作重點是跟蹤演算法的改進及其對IT公司經濟的影響。

另一位Neil Thompson是麻省理工大學CSAIL （計算機科學和人工智慧實驗室） 的科學家，也是 哈佛大學 創新科學實驗室的客座教授。

論文： https：//ieeexplore。ieee。org/document/9540991

參考連結： https：//news。mit。edu/2021/how-quickly-do-algorithms-improve-0920

— 完 —

量子位 QbitAI · 頭條號簽約

關注我們，第一時間獲知前沿科技動態