研究者的结果量化了算法改进影响计算机科学的两个重要教训 。
其一 ， 当一个算法族从指数级复杂度过渡到多项式复杂度时 ， 它会以一种硬件改进无法做到的方式转变该问题的易处理性；
其二 ， 随着问题规模增加至数十亿或万亿个数据点时 ， 就平均年改进率而言 ， 算法改进的重要性比硬件或摩尔定律重要得多 。 这些发现表明 ， 在拥有大规模数据集的数据分析和机器学习领域 ， 算法改进尤为重要 。
算法中的 Step 分析
在整篇文章中 ， 该研究通过查看算法的渐进复杂度来估算算法需要执行的 step 数 。
为了估计渐近复杂度近似的保真度 ， 该研究重新分析了算法改进的研究 。 由于数据库中只有 11% 的论文报告了算法所需的算法 step 数 ， 因此研究者需要尽可能根据原始论文中的伪代码描述手动重建 step 数 。
使用这种方法 ， 该研究能够重建 65% 的算法族中第一个和最后一个算法所需的算法 step 数 。 图 4 显示了算法 step 改进和渐近复杂度改进之间的比较 。
图 4 显示 ， 在数据可用的情况下 ， 算法 step 数和渐近性能的改进大小几乎相同 。
文章图片
参考链接：
https://news.mit.edu/2021/how-quickly-do-algorithms-improve-0920
https://ieeexplore.ieee.org/document/9540991
推荐阅读
- 制造业|稳健前行开新局 制造业未来五年转型升级迎来“加速度”
- 设计|宇瞻发布 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效果质量不减