该团队总共研究了 113 个算法族 ，对于每个算法 ， 该团队都重建了它的历史 ， 跟踪每次针对该问题所提出的新算法 ， 并特别强调那些更有效的算法 。 从 1940 年代到现在 ， 从性能上看 ， 该团队发现每个算法族平均有 8 个算法 ， 其中有几个提高了效率 。 为了共享这个知识数据库 ， 该团队还创建了 Algorithm-Wiki.org 。
此外 ， 该研究还绘制了这些算法族改进的速度 ， 他们重点关注那些算法中经常被用来分析的特征 ， 这些特征能保证以最快的速度解决问题 。
对于大型计算问题 ， 43% 的算法改进等于或大于摩尔定律带来的益处 。 在 14% 的问题中 ， 算法对性能的改进大大超过了硬件改进带来的益处 。 对于大数据问题 ， 算法改进带来的益处也非常大 ， 因此算法改进的重要性在近几十年来不断增加 。
Neil Thompson 与麻省理工学院访问学生 Yash Sherry 一起撰写了这篇论文 。 其中 Thompson 是麻省理工学院计算机科学和人工智能实验室研究科学家 ， 也是哈佛大学创新科学实验室的客座教授 。 他的主要研究领域包括摩尔定律与计算机性能、机器学习与算法等 。
Neil Thompson
文章图片
分析结果
在分析中 ， 研究者着重于具有精确解的精确算法 。 他们将算法分类为解决不同潜在问题的算法族 。 例如 ， 合并排序和冒泡排序是比较式排序族中 18 种算法中的两种 。 最终 ， 基于一系列标准 ， 研究者共探究了 113 个算法族 。
平均而言 ， 每个族有 8 种算法 。 如果一种算法降低了其算法族的最坏情况渐进时间复杂度 ， 则认为它改进了 。 基于这一标准 ， 研究中得到了 276 种初始算法和后续改进算法 ， 其中每个算法族中初始算法平均会有 1.44 个改进 。
创建新算法
下图 1 总结了随时间推移出现的算法发现和改进 。 其中 ， 1(a) 展示了每个算法族中首个算法出现的时间 ， 通常通过蛮力实现（意味着直接但计算效率低下） ， 1(b) 展示了每十年中算法的份额 ， 其中渐进时间复杂度提升 。
例如 ， 20 世纪 70 年代发现了 23 个新的算法族 ， 并对先前发现的所有算法族中的 34% 进行了改进 。 以后数十年 ， 发现和改进的速度下降了 ， 表明这些算法的进展放缓了 。 尚不清楚究竟是哪些原因造成的 ， 一种可能的原因是某些算法在理论上已经达到了最优 ， 因此不可能取得进一步发展 。
文章图片
下图 1 (c) 和 1(d) 分别展示了算法首次被发现时的「时间复杂度类别」分布以及因算法改进使得一类算法转变为另一类的概率 。 在算法理论中 ， 时间复杂度类别根据算法本身需要的操作数量（通常表示为输入大小函数）进行分类 。
推荐阅读
- 制造业|稳健前行开新局 制造业未来五年转型升级迎来“加速度”
- 设计|宇瞻发布 NOX 系列 DDR5 电竞内存，速度最高 7200MHz
- 数据|全球5G下载速度普遍下降，韩国、中国等除外
- 东西|手机越用越卡？是这5个东西在拖慢你的手机速度！
- 速度|长江存储发布PCle4.0 固态硬盘致态TiPro7000，顺序读取速度高达7400MB/s
- 通信技术|日本将试验激光与卫星通信 连接速度可达10Gbps
- ip|选择HTTP/S还是SOCKS5代理 谁的代理IP稳定速度快
- 长江|致钛新一代国产 SSD 明天发布：Pro 级速度，配备散热器
- Intel|英特尔已为Linux 5.17准备了一些Wi-Fi改进
- 模型|神经辐射场去掉「神经」，训练速度提升100多倍，3D效果质量不减