MIT证明：解决超大规模问题，算法比硬件更有用

软件在多大程度上提高了计算速度。

麻省理工学院的最新研究表明，种算法中有超过40%的算法提高了性能，这已经超过了硬件的摩尔定律。

对于中等规模的问题，30%—43%的算法改进比硬件改进更能提高性能。

当问题数据增加到上亿时，算法改进变得比硬件改进/摩尔定律更重要。

这是两位麻省理工学院科学家的结论，他们分析了来自57本教科书和超过1137篇研究论文的数据。

不仅如此，它们还全面描述了现有和历史算法何时被发现，如何改进，以及改进的规模。

14%算法的改善率超过1000%。

通过分析QS排名前20的计算机名校使用的课件，研究者总结出算法:的11个子领域。

组合学，统计学/机器学习，密码学，数值分析，数据库，操作系统，计算机网络，机器人学，信号处理，计算机图形/图像处理，生物信息学。

通过分析算法教科书，学术期刊和子领域发表论文的信息，研究人员划分了113个算法家族，平均每个家族有8个算法。

首先，他们统计了从1940年到现在各种算法的初始呈现时间，

根据这些算法首次提出时的时间复杂度。可以看出，31%的算法属于指数复杂度类别:

在时间复杂度的提升上，对于n=100万的问题规模，部分算法的提升率比硬件或摩尔定律提升了:

算法改进对四个算法族的影响。

当这种分析扩展到110个算法族时，可以看到对于中等规模的问题，只有18%的算法比硬件快。

但当问题规模达到几百万，几十亿甚至上万亿时，算法的改进速度就超过了硬件性能。

甚至14%算法家族的改善率都超过了1000%，远超硬件提升带来的性能提升。

A:n=一千b:n=一百万c:n=一亿。

Yash Sherry毕业于印度德里大学计算机科学专业，现为麻省理工学院斯隆商学院研究员，专注于跟踪算法改进及其对IT公司经济的影响。

另一位尼尔汤普森是麻省理工学院CSAIL的科学家，也是哈佛大学创新科学实验室的客座教授。