MIT新研究43算法改进速度超摩尔定律，解决超大规模问题，算法比硬件更有用

　　软件算法对计算速度的提升有多大？
　　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