4.1. 章节引言¶

当我们完成计划中的合并后，处理公司工资单需要多长时间？我该从供应商 X 还是供应商 Y 购买新的工资单程序？如果某个程序很慢，是它的实现很糟糕，还是它要解决的问题本身很难？诸如此类的问题要求我们考虑一个问题的难度，或者求解同一问题的两种或多种方法的相对效率。

本章介绍算法分析的动机、基本记法和基本技术。我们关注一种称为 渐近算法分析 的方法，或简称为 渐近分析 。渐近分析试图估算一个算法的资源消耗。它让我们能够比较求解同一问题的两种或多种算法的相对成本。渐近分析还为算法设计者提供了一种工具，使他们能在实现实际程序之前，估算某个候选方案是否可能满足问题的资源约束。读完本章后，你应当理解

• 增长率 的概念， 即算法的成本随其输入规模增大而增长的速率；

• 增长率的 上界 和 下界 的概念， 以及如何为简单的程序、算法或问题估算这些界；以及

• 算法 （或程序）的成本与 问题 的成本 之间的区别。

本章最后简要讨论通过实验测量程序成本时遇到的实际困难，以及为提高程序效率而进行代码调优的一些原则。