软件算法对计算速度的提升有多大？
最新研究显示，超过40%的性能改进来自算法，而非硬件的摩尔定律带来的增速。
对于中等规模的问题，约30%到43%的性能提升来自算法改进，往往超过硬件进步的作用。
当问题数据规模达到数亿级别时，算法改进变得比硬件进步更关键。
这是基于对57本教材和超过1137篇研究论文的数据分析所得出的结论，研究由两位科学家完成。
研究者还系统梳理了现有及历史上的算法何时被发现、如何改进，以及改进的规模。
有14%的算法改进率超过1000%，显示出算法进步的潜力之大。
通过分析QS排名前20的计算机名校所用的课程资料，研究者总结出11个算法子领域：
– 组合学、统计学/机器学习、密码学、数值分析、数据库、操作系统、计算机网络、机器人学、信号处理、计算机图形/图像处理、生物信息学。
在这些子领域的教材、学术期刊及论文信息基础上，研究者划分出113个算法家族，平均每个家族含8个算法。
研究首先统计了从1940年至今，各种算法的最初提出时间：
并据此对算法初始时的时间复杂度进行了归纳。结果显示，其中31%的算法属于指数复杂度类别：
在时间复杂度的改进方面，对于规模为n=100万的问题，一些算法的改进率甚至超越硬件或摩尔定律的提升速度：
若将分析扩展到110个算法家族，对于中等规模（n=1000）的问题而言，只有18%的算法改进速度快于硬件。
但当问题规模达到百万、亿、乃至万亿级别时，算法的改进速度就超过了硬件性能。
甚至有14%的算法家族的改进率超过1000%，远超硬件改进带来的性能提升。
作者介绍
论文第一作者Yash SheRRy，本科毕业于印度德里大学计算机科学专业，目前在某商学院担任研究员，研究方向聚焦算法改进及其对IT企业经济影响。
另一位作者
Neil ThoMpson，来自某知名高校的计算机科学领域专家，也在其他机构担任客座教授。
论文信息
论文链接： https://ieeexplore.ieee.org/document/9540991
