軟件算法對計算速度的提升有多大？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