为什么对数的增长速度比任何多项式都慢?什么是(可以理解的)证明?
相似地,
为什么指数总是比任何多项式增长得快?
编辑:这个答案本质上是在做 PengOne 所说的。
我们取极限
log_2(x) / x^p
对于常数 p > 0 并表明极限为零。由于随着 x 无限增长,log_2(x) 和 x^p 都趋于无穷大,因此我们应用l'Hopital 规则。这意味着我们的限制与
1/(x*ln2) / p*x^(p-1)
使用简单的分数规则,我们将其简化为
1 / (p * x^p * ln2)
由于分母趋于无穷大而分子不变,我们可以评估极限——它为零,这意味着无论 p 的(正)值如何,log_2(x) 的渐近增长都比 x^p 慢。
编辑2:
顺便说一句,如果您对这个问题和发布的答案感兴趣,请考虑通过点击此链接并承诺支持新的 Computer Science StackExchange 站点:
给定两个(非负)实值函数f
和g
,您要计算
lim_{x -> infinity} f(x) / g(x)
这个限制是:
0
当且仅当f
增长慢于g
infinity
当且仅当f
增长快于g
c
对于某个常数0 < c < infinity
当且仅当f
并且g
以相同的速度增长现在,您可以采用任何您喜欢的示例并计算限制以查看哪个增长更快。
你可以考虑衍生产品。
d(x^n)/dx = nx^(n-1)
d(ln x)/dx = 1/x
对于 n >= 1 nx^(n-1) 随 x 增加或保持不变,而 1/x 随 x 减少,因此多项式增长更快。
e^x 的对数是 x,而 n^x 的对数是 n ln x,所以用上面的论点比较 e^x 的对数和 x^n 的对数,e^x 增长得更快。