1

为什么对数的增长速度比任何多项式都慢?什么是(可以理解的)证明?

相似地,

为什么指数总是比任何多项式增长得快?

4

3 回答 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 站点:

http://area51.stackexchange.com/proposals/35636/computer-science-non-programming?referrer=rpnXA1_2BNYzXN85c5ibxQ2

于 2012-01-11T19:32:44.903 回答
1

给定两个(非负)实值函数fg,您要计算

lim_{x -> infinity} f(x) / g(x)

这个限制是:

  • 0当且仅当f增长慢于g
  • infinity当且仅当f增长快于g
  • c对于某个常数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 回答