算法与硬件

概述

算法与硬件 的关系表明，算法层面的进步可以与甚至超越硬件升级带来的性能提升，是推动计算能力发展的双重驱动力。

定义

算法与硬件的互补性

计算性能的提升不仅来自硬件（更快的处理器、更大的内存），也来自更高效的算法。在某些场景下，算法改进带来的加速远超硬件升级。

核心性质

• 摩尔定律：硬件性能约每18-24个月翻倍，但这一趋势在近年逐渐放缓
• 算法加速的持久性：硬件升级的效果会随时间被新硬件取代，但算法改进是永久的——更好的算法在任何硬件上都能带来加速
• Strassen算法实例：Strassen算法将矩阵乘法从 $\Theta (n^3)$ 降至 $\Theta (n^{2.81})$。对于 $n=1024$，加速比约为 $1024^{0.19}\approx 4.7$ 倍，相当于数代硬件升级
• 复合效应：算法改进与硬件升级可以叠加，产生复合加速效果
• 规模效应：问题规模越大，算法改进的加速效果越显著（多项式 vs 多项式的指数差异）

章节扩展

第1章：1.2 算法作为一种技术通过多个实例说明算法进步的实际影响力，强调算法研究不仅是理论追求，更是工程实践中的关键竞争力。

参见

• 1.2 算法作为一种技术 — 算法作为技术的详细论述
• Strassen算法 — 算法超越硬件加速的经典案例