3. 增长率回顾¶
3.1. 增长率回顾¶
\(n\) 的两个函数具有不同的 增长率，如果当 \(n\) 趋于无穷时， 它们的比值要么趋于无穷，要么趋于零。
Figure 21.3.1: 一个图的两个视图，展示了 六个方程的增长率。 下面的视图详细显示了上面视图的左下部分。 水平轴表示输入规模。 垂直轴可以表示时间、空间或任何其他代价度量。¶
方程 \((1.618)^n\) 的线在这张图上会放在哪里？
把程序操作与运行时间联系起来的精确方程需要 依赖机器的常数。 有时，精确运行时间的方程很难计算。 通常，我们满足于知道一个近似的增长率。 具体来说，我们一般不关心方程中的常数。 给定增长率分别为 \(c_1n\) 和 \(c_2 2^{n!}\) 的两个算法， 我们需要知道 \(c_1\) 和 \(c_2\) 的值吗？
这里有一些有用的观察。
既然 \(n^2\) 比 \(n\) 增长得快，
\(2^{n^2}\) 比 \(2^n\) 增长得快。 （两边取反对数。）
\(n^4\) 比 \(n^2\) 增长得快。 （两边平方。）
\(n\) 比 \(\sqrt{n}\) 增长得快。 （\(n = (\sqrt{n})^2\)。 把 \(n\) 替换成 \(\sqrt{n}\)。）
- :math:`2 log n` 增长得 不比* \(\log n\) 慢。
（两边取 \(\log\)。对数会"抹平"增长率。）
既然 \(n!\) 比 \(2^n\) 增长得快，
\(n!!\) 比 \(2^n!\) 增长得快。 （两边取阶乘。）
\(2^{n!}\) 比 \(2^{2^n}\) 增长得快。 （两边取反对数。）
\(n!^2\) 比 \(2^{2n}\) 增长得快。 （两边平方。）
\(\sqrt{n!}\) 比 \(\sqrt{2^n}\) 增长得快。 （两边开平方。）
- :math:`log n!` 增长得 不比* \(n\) 慢。
（两边取对数。 实际上，它增长得更快，因为 \(\log n! = \Theta(n \log n)\)。）
如果 \(f\) 比 \(g\) 增长得快，那么 \(\sqrt{f}\) 一定比 \(\sqrt{g}\) 增长得快吗？ 是的。
\(\log f\) 一定比 \(\log g\) 增长得快吗？ 不。 \(\log n \approx \log n^2\) 相差一个常数因子，也就是说， 增长 率 相同！ 同样是这个道理，取对数操作会"抹平"相对的增长率。
\(\log n\) 与 \(n\) 的关系，与 \(n\) 和 \(2^n\) 的关系完全一样。
\(2^{\log n} = n\)。
3.1.1. 渐近记法¶
记法 "\(f \in O(n^2)\)" 比 "\(f = O(n^2)\)" 更受青睐。 虽然 \(n \in O(n^2)\) 且 \(n^2 \in O(n^2)\)， 但 \(O(n) \neq O(n^2)\)。
注意 Big oh 并没有说明一个算法有多好—它只说明算法 可能 有多坏。
如果算法 \(\mathcal{A}\in O(n)\) 而算法 \(\mathcal{B} \in O(n^2)\)， \(\mathcal{A}\) 比 \(\mathcal{B}\) 好吗？ 也许……但也许问题在于我们对这些算法的分析了解不多。 也许更精确的分析会表明 \(\mathcal{A} = \Theta(n)\) 而 \(\mathcal{B} = \Theta(\log n)\)。
一些对数记法：\(\log n^2 (= 2 \log n)\)、 \(\log^2 n (= (\log n)^2)\) 与 \(\log \log n\)。
\(\log 16^2 = 2 \log 16 = 8\)。
\(\log^2 16 = 4^2 = 16\)。
\(\log \log 16 = \log 4 = 2\)。
阶记法有实际限制。 考虑这样的说法： 算法 \(\mathcal{A}\) 的资源需求 比算法 \(\mathcal{B}\) 的资源需求增长得慢。 \(\mathcal{A}\) 是否 优于 \(\mathcal{B}\)？ 这样断言存在一些潜在问题。
输入必须多大，这个说法才成立？
有些增长率差异是微不足道的。 例如：\(\Theta(\log^2 n)\) 与 \(\Theta(n^{1/10})\)。 如果 \(n\) 是 \(10^{12} (\approx 2^{40})\)，那么 \(\log^2 n \approx 1600\)，\(n^{1/10} = 16\)，尽管 \(n^{1/10}\) 比 \(\log^2 n\) 增长得快。 要让 \(n^{1/10}\) 大于 \(\log^2 n\)，\(n\) 必须 极其巨大（比如 \(2^{150}\)）。
降低算法的增长率并不总是"实际"可行的。 这里的"实际"意味着，当我们削掉次要的渐近增长时， 常数可能会变得过高。 削掉一个 \(n\) 的因子，对于一百万规模的输入， 就把代价降低了一百万倍。 削掉一个 \(\log \log n\) 的因子，只节省 4-5 倍。 所以如果改变算法以去除一个 \(\log \log n\) 因子 却要付出 10 倍常数的代价，那么新算法 （虽然渐近意义上更好）要等到 \(n\) 大到在任何真实情形 中都不会使用的地步，才能体现其优势。
这引出了 实用性窗口 的概念。 一般而言，（1）我们求解问题的时间有限， （2）在计算机不堪重负之前（或者至少，用户只对 运行一定规模的问题感兴趣），输入只能长到这么大。 所以虽然一个算法可能渐近意义上优于另一个， 但在用户实际需要求出的实际输入范围内，也许并不成立。
幸运的是，算法的增长率 通常 表现得很好，所以 阶记法能给出实际的指示。 "实际"是关键词。 我们使用渐近分析，是因为它提供了一个简单的 模型 ， 通常 能反映现实。 这 有助于 简化我们的思考。
