增长速度：指数、幂与对数的快慢

比较函数的增长快慢，比较的不是某一点的函数值，而是 $x \to +\infty$ 时谁最终占优。对 $a > 1$、$n > 0$ 的指数函数 $y = a^x$、幂函数 $y = x^n$ 与对数函数 $y = \log_a x$，结论是一条固定的次序：指数终将超过幂，幂终将超过对数，且一旦超过就不再被追上。「终将」二字承担了全部的分量——它只断言存在一个分界点，对分界点的位置只字未提。

1 · 最终次序的表述

准确的说法用极限写：$\lim_{x \to +\infty} \dfrac{x^n}{a^x} = 0$ 与 $\lim_{x \to +\infty} \dfrac{\log_a x}{x^n} = 0$，对任意 $a > 1$ 与任意 $n > 0$ 成立。高中阶段不做极限证明，代之以「存在 $x_0$，当 $x > x_0$ 时 $a^x > x^n$ 恒成立」这一等价说法。$n$ 取多大都无所谓：$n = 100$ 时分界点向右挪得很远，但它仍然是一个有限的数。

复利、细胞分裂与算法的指数级枚举都归在同一条曲线上，这也是「指数增长」在日常语境里被用作剧烈变化代名词的由来。

2 · 有限区间内的次序反转

在分界点左侧，次序可以完全颠倒，而分界点的位置未必大。$y = 2^x$ 与 $y = x^2$ 在正半轴上交于 $x = 2$ 与 $x = 4$ 两处，两个交点都是整数：$2^2 = 2^2$ 与 $2^4 = 4^2$。在 $(2, 4)$ 这段区间上幂函数反而在上方，$x = 3$ 处 $2^3 = 8$ 小于 $3^2 = 9$。越过 $x = 4$ 之后指数函数才一路领先。

3 · 反超点的位置

反超点对参数极为敏感，几组实测值列在下表。第二个交点即最终的分界点，它之后指数函数不再被追上。

底取 3 而幂次取 2 时两条曲线在扫描区间内不相交，$3^x$ 全程在 $x^2$ 之上。这句话只对正半轴成立：$x$ 取 $-1$ 时 $3^{-1} = 0.333$ 已小于 $(-1)^2 = 1$，交点落在 $-0.8$ 与 $-0.6$ 之间，在表格的扫描范围 $[0.05, 60]$ 之外。底降到 1.5、幂次升到 5，分界点便推到 47.6。表中 $a = 2$、$n = 4$ 那一行的 16.000 不是舍入的巧合：$2^{16} = 65536 = 16^4$，两个数严格相等。

对数一侧的分界点还要靠后。$y = \log_2 x$ 与 $y = x^{0.2}$ 在 $x = 2.26$ 处相交后，对数一路压在幂函数上方，直到 $x \approx 5.69 \times 10^{6}$ 才被反超。若只在 $x < 10^{6}$ 的范围内取数据作图，得到的结论会与「幂终将超过对数」正好相反。这类反例说明，把有限区间上的观察外推成渐近结论是不可靠的；反过来，用渐近结论去预测有限区间内的表现同样不可靠。

4 · 参考文献

1. Exponential growth. Wikipedia. 指数增长与它同幂增长的比较。https://en.wikipedia.org/wiki/Exponential_growth
2. Asymptotic analysis. Wikipedia. 「最终占优」的严格含义与渐近记号。https://en.wikipedia.org/wiki/Asymptotic_analysis
3. Orders of approximation. Wikipedia. 有限区间上的观察为何不能外推成渐近结论。https://en.wikipedia.org/wiki/Orders_of_approximation