算法设计是开发解决问题的数学过程。算法分析是预测算法的性能。前面两章介绍了经典的数据结构（列表、堆栈、队列、优先级队列、集合和映射）并应用它们来解决问题。本章将使用各种示例来介绍用于开发高效算法的常用算法技术（动态规划、分而治之和回溯）。

Big O表示法获得了一个根据输入大小衡量算法时间复杂度的函数。您可以忽略函数中的乘法常数和非支配项。假设两种算法执行相同的任务，例如搜索（线性搜索与二分搜索）。哪一个更好？要回答这个问题，您可以实现这些算法并运行程序以获得执行时间。但这种方法有两个问题：

• 首先，许多任务在计算机上同时运行。特定程序的执行时间取决于系统负载。
• 其次，执行时间取决于具体的输入。例如，考虑线性搜索和二分搜索。如果要搜索的元素恰好是列表中的第一个元素，线性搜索将比二分搜索更快地找到该元素。

通过测量算法的执行时间来比较算法是非常困难的。为了克服这些问题，开发了一种理论方法来分析独立于计算机和特定输入的算法。这种方法近似改变输入大小的影响。通过这种方式，您可以看到算法的执行时间随着输入大小的增加而增加的速度，因此您可以通过检查两个算法的增长率。

考虑线性搜索。线性搜索算法将键与数组中的元素顺序进行比较，直到找到键或数组耗尽。如果键不在数组中，则需要对大小为 n 的数组进行 n 比较。如果键在数组中，则平均需要 n/2 次比较。该算法的执行时间与数组的大小成正比。如果将数组大小加倍，则比较次数也会加倍。该算法以线性速率增长。增长率的数量级为n。计算机科学家使用大 O 符号来表示“数量级”。使用这种表示法，线性搜索算法的复杂度为 O(n)，发音为“n阶”。我们将时间复杂度为 O(n) 的算法称为线性算法，并且它呈现出线性增长率。

对于相同的输入大小，算法的执行时间可能会有所不同，具体取决于输入。导致执行时间最短的输入称为最佳情况输入，导致执行时间最长的输入称为最坏情况输入。最佳案例分析和
最坏情况分析是分析算法的最佳情况输入和最坏情况输入。最好情况和最坏情况分析不具有代表性，但最坏情况分析非常有用。您可以放心，该算法永远不会比最坏情况慢。
平均情况分析尝试确定相同大小的所有可能输入之间的平均时间量。平均情况分析是理想的，但很难执行，因为对于许多问题来说，很难确定各种输入实例的相对概率和分布。最坏情况分析比较容易进行，所以一般都是针对最坏情况进行分析。

如果您几乎总是在查找列表中已知的内容，则线性搜索算法在最坏情况下需要 n 次比较，在平均情况下需要 n/2 次比较。使用 Big O 表示法，两种情况都需要 O(n) 时间。乘法常数 (1/2) 可以省略。算法分析的重点是增长率。乘法常数对增长率没有影响。 n/2 或 100_n_ 的增长率与 n 相同，如下表 增长率 所示。因此，O(n) = O(n/2) = O(100n).

考虑在 n 个元素的数组中查找最大数字的算法。如果n为2，则需要比较一次才能找到最大数；如果n为3，则进行两次比较。一般来说，需要 n - 1 次比较才能找到 n 个元素列表中的最大数量。算法分析适用于大输入量。如果输入量很小，那么估计算法的效率就没有意义。随着 n 变大，表达式 n - 1 中的 n 部分在复杂性上占主导地位。大 O 表示法允许您忽略非主导部分（例如，
中的 -1 表达式 n - 1）并突出显示重要部分（例如，表达式 n - 1 中的 n）。因此，该算法的复杂度为O(n)。

Big O 表示法根据输入大小估计算法的执行时间。如果时间与输入大小无关，则该算法被称为采用恒定时间，符号为O(1)。例如，检索数组中给定索引处的元素的方法
需要常数时间，因为时间不会随着数组大小的增加而增加。

以下数学求和在算法分析中通常很有用：

时间复杂度是使用 Big-O 表示法来衡量执行时间。同样，您还可以使用 Big-O 表示法来测量空间复杂度。 空间复杂度衡量算法使用的内存空间量。书中介绍的大多数算法的空间复杂度都是 O(n)。即，它们对输入大小表现出线性增长率。例如，线性搜索的空间复杂度为 O(n).