1. 章节引言¶

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

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

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

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

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

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