计算机科学：算法改进速度有多快？研究发现将超过摩尔定律

算法有点像计算机的父母，它们告诉计算机如何处理信息，使计算机反过来从信息中做找出有用的东西。算法的效率越高，计算机需要做的工作就越少。

算法正在被改进中。虽然算法的效率可能不那么引人注目，但如果你常用的搜索引擎的处理速度突然只有十分之一，你一定会注意到。

这不禁使麻省理工学院计算机科学和人工智能实验室（CSAIL）的科学家们提出：算法的改进速度有多快？ 

这个问题的现有数据大多都不成立，因为这些数据都是由特定算法的案例研究组成。由于缺乏证据，该团队开始从57本教科书和超过1110篇研究论文中压缩数据，以追踪算法的变更历史。

该团队总共研究了113个计算机科学教科书中最重要的“算法家族”。算法家族就是解决同一问题的一组算法。研究小组重建了113种算法中每一种的历史，跟踪了每次提出的新算法，还特别关注了更高效的算法。从20世纪40年代到现在的几十年间，该团队发现每个家族平均有8种算法，其中有些算法会提高效率。为了分享这个知识数据库，该团队还创建了Algorithm-Wiki.org。

科学家们绘制了这些家族改进速度的图表，重点分析了算法最主要的特征，即它们能够保证解决问题的最快速度，用计算机术语来说就是“最坏情况时间复杂度”。

对于大型计算问题，43%的算法家族的同比改进等于或大于摩尔定律带来的收益。摩尔定律是指处理器的性能每隔两年翻一倍。在14%的问题中，算法对性能的改进大大超过了硬件改进所带来的受益。此外，对于大数据问题来说，来自算法改进带来的收益巨大。

作者观察到的最大变化是算法家族从指数级时间复杂度过渡到多项式时间复杂度。解决一个指数级问题就像一个人试图猜测一把锁的密码。如果你只有一个10位数的表盘，这个任务很容易。如果有像自行车锁那样的四个表盘，就没有人能偷你的自行车，但他仍然可以猜测到你可以尝试的每一种组合。如果是50个表盘，偷车几乎是不可能的。具有指数级复杂度的问题对计算机来说也是如此。随着它们变得越来越大，它们很快就会超过计算机的处理能力。而找到一个多项式算法往往可以解决这个问题。

随着摩尔定律时代即将结束，研究人员说，计算用户将越来越需要算法来提高性能。该团队说，研究结果证实，从历史上看，来自算法的收益是巨大的。来自摩尔定律的硬件改进会随着时间的推移而逐渐改变。而对于算法来说，收益是一步一步来的，通常巨大但不频繁。

通过分析发现，算法改进后，使用同等计算能力可以完成更多的任务。随着问题增加到数十亿或数万亿的数据点，算法的改进将比硬件的改进更加重要。

该研究论文题为"How Fast Do Algorithms Improve"，已发表在Proceedings of the IEEE期刊上。主要作者为Yash Sherry和Neil C. Thompson。

前瞻经济学人APP资讯组

参考资料：https://ieeexplore.ieee.org/document/9540991