软件算法对计算速度的提升有多大？

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（计算机科学和人工智能实验室）的科学家，也是哈佛大学创新科学实验室的客座教授。