算法效率

概述

算法效率 是对算法消耗计算资源的度量，主要包括时间效率和空间效率，二者之间常存在权衡关系。

定义

算法效率

算法效率衡量算法解决特定规模问题所需的计算资源量随输入规模 $n$ 增长的速率，核心关注资源消耗的增长趋势而非绝对值。

核心性质

• 时间效率：算法执行所需的时间，通常用基本操作次数衡量。
• 空间效率：算法执行所需的辅助存储空间。
• 算法效率的改进往往比硬件升级带来更显著的性能提升（如 $\Theta (n^2)$ 到 $\Theta (n\lg n)$）。
• 时间与空间常存在权衡（trade-off）：可用更多空间换取更少时间，或反之。
• CLRS 强调：好的算法是驱动技术进步的核心力量，而不仅仅是硬件性能的提升。

章节扩展

第1章：算法在计算中的角色

• 1.2 算法作为一种技术 通过插入排序与归并排序的对比，展示算法效率对实际应用的巨大影响。

参见

• 渐近分析
• 渐近记号
• 大O记号