为什么对数的增长速度比任何多项式都慢？什么是（可以理解的）证明？
相似地，
为什么指数总是比任何多项式增长得快？
问问题
231 次
3 回答
3
编辑：这个答案本质上是在做 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 站点：
于 2012-01-11T19:32:44.903 回答
1
给定两个（非负）实值函数f和g，您要计算
lim_{x -> infinity} f(x) / g(x)
这个限制是：
0当且仅当f增长慢于ginfinity当且仅当f增长快于gc对于某个常数0 < c < infinity当且仅当f并且g以相同的速度增长
现在，您可以采用任何您喜欢的示例并计算限制以查看哪个增长更快。
于 2012-01-11T19:18:51.013 回答
0
你可以考虑衍生产品。
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 增长得更快。
于 2012-01-11T19:30:15.363 回答