MIT新研究：过去80年，算法效率提升到底有多快？新智元报道来源：MIT编辑：D

文章图片
新智元报道
来源：MIT
编辑：David
【新智元导读】随着摩尔定律走向终结，靠提升计算机硬件性能可能越发难以满足海量计算的需要，未来的解决之道在于提升算法的效率。 MIT的这篇新论文总结了过去80年来，算法效率的提升究竟有多快。
提起算法，它有点像计算机的父母，它会告诉计算机如何理解信息，而计算机反过来可以从算法中获得有用的东西。
【MIT新研究：过去80年，算法效率提升到底有多快？】算法的效率越高，计算机要做的工作就越少。对于计算机硬件的所有技术进步，以及备受争议的摩尔定律的寿命问题来说，计算机硬件的性能只是问题的一方面。
而问题另一方面则在硬件之外：算法的效率问题。如果算法的效率提升了，对同一计算任务需要的算力就会降低。
虽然算法效率问题可能不太受关注，但你是否注意到，经常使用的搜索引擎是否突然变快了十分之一，而在大型数据集中活动，就感觉就像在泥泞中跋涉一样艰难缓慢。
这些都与算法效率有关。

文章图片
近日，麻省理工学院计算机科学与人工智能实验室(CSAIL)的科学家提出疑问：算法效率的提升速度到底有多快？
关于这个问题，现有数据大部分是叙事性的，其中很大一部分是面向特定算法的案例研究，再把这些研究结果加以推广。
面对实证研究数据的不足，研究团队主要利用了来自57部教科书和1110多篇研究论文的数据，以追溯算法效率提升的历史。
其中有些论文的结论中直接给出了新的算法有多高效，有的论文则需要作者使用“伪代码”（对算法基本细节的简单描述）进行重构。
研究人员总共研究了113个“算法系” ，即解决计算机科学教科书中最重要的同一问题的算法集。他们对每个算法族的历史进行了回顾，跟踪每次针对某一问题提出的新算法，并特别注意更高效的算法。

文章图片
图1算法发现和改进。 (a)每十年发现的新算法系的数量。 (b)已知算法系的比例每十年都有所提高。 (c)首次发现时算法系的渐近时间复杂度分类。 (d)同一时间复杂度的算法转换到另一个时间复杂度的每年平均概率（反应算法系复杂度提升的平均水平）。在（c）和（d）中“>n3”的时间复杂度表示超过多项式级，但不到指数级。
最早的算法系可追溯到上世纪40年代，每个算法系平均有8个算法，按时间顺序效率逐步提升。为了共享这一发现，团队还创建了“算法维基”页面（Algorithm-Wiki.org）。
研究人员绘制了图表，标识这些算法族效率提升的速度，重点关注算法分析最多的特征——这些特征往往决定了解决问题的速度有多快（用计算机术语说，就是“最坏情况下的时间复杂度”）。

文章图片
图2算法系的相对效率提升，使用渐近时间复杂度的变化计算。参考线是SPECInt基准性能。 (a)与该系列中的第一个算法（n=100万）相比，四个算法系的历史改进。 (b)算法改进对“最近邻搜索”算法系列的输入大小(n)的敏感度。为了便于比较算法改进效果随时间的变化，在图(b)中将算法系和硬件基准的起始时间段对齐。
结果显示，变数很大，但也发现了关于计算机科学变革性算法效率提升的重要信息。即：