6. 渐近分析与上界¶
6.1. 渐近分析与上界¶
尽管上图中标记为 \(10 n\) 的曲线带有更大的常数，\(2 n^2\) 还是会在相当小的 \(n = 5\) 处与之相交。 如果把线性方程前面的常数翻倍会怎样？ 如图所示，一旦 \(n = 10\) ，\(2 n^2\) 就会超过 \(20 n\) 。 线性 增长率 上多出的因子 2 并不要紧，它只是把交点的 \(x\) 坐标翻倍而已。 一般地，改变任一方程中的常数因子，只会移动两条曲线相交的 位置 ，而不会改变两条曲线 是否 相交。
当你买到更快的计算机或更快的编译器时，对于给定的增长率，在给定时间内所能运行的问题规模会以相同的倍数变大，而与运行时间方程中的常数无关。 增长率不同的两个算法，其时间曲线仍会相交，与它们运行时间方程中的常数无关。 出于这些原因，当我们想估计算法运行时间或其他资源需求的增长率时，通常会忽略常数。 这简化了分析，并让我们始终关注最重要的方面：增长率。 这称为 渐近算法分析 。 准确地说，渐近分析研究的是输入规模"变得很大"或趋于某个极限（微积分意义上的极限）时的算法。 然而，实践证明忽略所有常数因子非常有用，因此大多数算法比较都采用渐近分析。
在少数情况下，忽略常数并不合理。 当比较旨在处理较小 \(n\) 值的算法时，常数可能产生很大影响。 例如，如果问题要求你对许多恰好包含五条记录的集合排序，那么为排序数千条记录而设计的排序算法多半不合适，即使其渐近分析表明性能良好。 在罕见的情况下，参与比较的两个算法的常数可能相差 1000 倍甚至更多，使得增长率较低的那个算法因其常数过大而在典型问题规模下不实用。 渐近分析是对算法资源消耗的一种"信封背面"式的 estimation （粗略估算）。 它为算法的运行时间或其他资源需求提供了一个简化模型。 这种简化通常有助于你理解自己算法的行为。 只需注意，在常数很重要的罕见情形下，渐近分析有其局限性。
6.1.1. 上界¶
有若干术语用于描述算法的运行时间方程。 这些术语—及其相关符号—精确地表明所描述的是算法行为的哪个方面。 其一是算法运行时间增长的 上界 。 它表示该算法可能具有的上限，即最高增长率。
由于"算法的增长率具有上界 \(f(n)\)"这一说法很长，而在讨论算法时又经常用到，我们采用一种特殊的记法，称为 大 O 记法 。 如果某算法增长率的上界（比如在最坏情况下）是 (f(n))，我们就写成：该算法在最坏情况下属于集合 \(O(f(n))\) （或简写为：在最坏情况下属于 \(O(f(n))\) ）。 例如，如果对最坏情况的输入，\(n^2\) 与 \(\mathbf{T}(n)\) （我们算法的运行时间）增长得一样快，我们就说该算法"在最坏情况下属于 \(O(n^2)\) "。
下面给出上界的精确定义。 \(\mathbf{T}(n)\) 表示算法的真实运行时间。 \(f(n)\) 是表示上界的某个表达式。
若 \(\mathbf{T}(n)\) 是非负值函数，则当存在两个正常数 \(c\) 和 \(n_0\) ，使得对所有 \(n > n_0\) 都有 \(\mathbf{T}(n) \leq cf(n)\) 时，\(\mathbf{T}(n)\) 属于集合 \(O(f(n))\) 。
常数 \(n_0\) 是使命题成立的最小 \(n\) 值。 通常 \(n_0\) 很小，比如 1，但也不必如此。 你还必须能够选取某个常数 \(c\) ，但 \(c\) 的实际取值无关紧要。 换言之，该定义说的是：对于所考虑类型中足够大的 所有 输入（例如规模为 \(n\) 的所有输入在最坏情况下，即 \(n > n_0\) 时），该算法 总是 以不超过 \(cf(n)\) 步（对某个常数 \(c\) ）执行完毕。
如果有人突然问你"谁是最好的？"，你的自然反应应该是反问"在什么方面最好？"。 同样，如果有人问你"这个算法的增长率是多少"，你需要追问"什么时候？最好情况？平均情况？还是最坏情况？"。 有些算法无论收到给定规模的哪个输入实例，行为都一样，例如在整数数组中求最大值。 但对许多算法来说，涉及给定规模中的哪个具体输入会带来很大差别，例如在未排序的数组中查找某个特定值时。 因此，关于算法上界的任何表述，都必须限定在规模为 \(n\) 的某个特定输入类别的语境中。 我们几乎总是在最好情况、平均情况或最坏情况的输入上度量这个上界。 所以，我们不能说"该算法的增长率具有上界 \(n^2\) "，因为这样的表述不完整。 我们必须说成"该算法的增长率 在平均情况下 具有上界 \(n^2\) "。
知道某算法属于 \(O(f(n))\) 只能说明情况最坏能糟到什么程度，实际情况也许远没有那么糟。 因为顺序查找在最坏情况下属于 \(O(n)\) ，所以说顺序查找属于 \(O(n^2)\) 也同样成立。 但当 \(n\) 很大时，顺序查找是实用的，而对某些属于 \(O(n^2)\) 的其他算法来说却并非如此。 我们总是力求用尽可能紧确（最低）的上界来刻画算法的运行时间。 因此，我们更愿意说顺序查找属于 \(O(n)\) 。 这也解释了为什么使用"属于 \(O(f(n))\)"这一说法或记号 \(\in O(f(n))\) ，而不使用"是 \(O(f(n))\)"或 \(= O(f(n))\) 。 使用大 O 记法并不意味着严格相等。 \(O(n)\) 包含于 \(O(n^2)\) ，但 \(O(n^2)\) 不包含于 \(O(n)\) 。
6.1.2. 简化规则¶
一旦确定了算法的运行时间方程，从方程推导大 O 表达式其实很简单。 你不必借助渐近分析的正式定义，而可以使用下面的规则来确定最简形式。
如果 \(f(n)\) 属于 \(O(g(n))\) 且 \(g(n)\) 属于 \(O(h(n))\) ，那么 \(f(n)\) 属于 \(O(h(n))\) 。
如果对任意常数 \(k > 0\) 都有 \(f(n)\) 属于 \(O(k g(n))\) ，那么 \(f(n)\) 属于 \(O(g(n))\) 。
如果 \(f_1(n)\) 属于 \(O(g_1(n))\) 且 \(f_2(n)\) 属于 \(O(g_2(n))\) ，那么 \(f_1(n) + f_2(n)\) 属于 \(O(\max(g_1(n), g_2(n)))\) 。
如果 \(f_1(n)\) 属于 \(O(g_1(n))\) 且 \(f_2(n)\) 属于 \(O(g_2(n))\) ，那么 \(f_1(n) f_2(n)\) 属于 \(O(g_1(n) g_2(n))\) 。
第一条规则说明：如果某个函数 \(g(n)\) 是你的代价函数的一个上界，那么 \(g(n)\) 的任何上界也是你的代价函数的上界。
规则 (2) 的意义在于：使用大 O 记法时，可以忽略方程中任何乘法常数。
规则 (3) 说明：给定程序中顺序执行的两个部分（无论是两条语句还是两段代码），只需考虑代价更高的那部分。
规则 (4) 用于分析程序中的简单循环。 如果某个动作重复若干次，且每次重复的代价相同，那么总代价就是该动作的代价乘以该动作发生的次数。
综合前三条规则，你可以忽略所有常数和所有低阶项，从而确定任何代价函数的渐近增长率。 忽略常数的好处与危险已在本节开头附近讨论过。 做渐近分析时忽略低阶项是合理的：随着 (n) 变大，高阶项对总代价的贡献很快就淹没低阶项。 因此，如果 \(\mathbf{T}(n) = 3 n^4 + 5 n^2\) ，那么 \(\mathbf{T}(n)\) 属于 \(O(n^4)\) 。 当 \(n\) 很大时，\(n^2\) 项对总代价的贡献相对很小。
从现在起，在讨论程序或算法的代价时，我们将使用这些简化规则。
