比较两个函数的增长率。（有技巧）

Question

我需要比较以下函数的增长率：

f(n)=2^n 和 g(n)=n^log(n) (当 n 趋近正无穷时)。

这是否可能呢？

- John Doe

Answer 1

让 n = 2^k。我们有：

2^n = 2^(2^k)
n^log(n) = (2^k)^log(2^k) = (2^k)^(k log 2)
         = 2^(k^2 log 2)

现在比较 2^k 和 k^2 log 2。这是一个基本的比较：当 k 足够大时，2^k 更大。

- IVlad

---

哇，这是一个有趣的方法。不过有一件事我不明白，这是怎么发生的？(2^k)^(k log 2)= 2^(k^2 log 2) - John Doe

@JohnDoe 这只是“幂的幂”属性：(a^x)^y = a^(x*y)。这里有一个例子：http://www.icoachmath.com/math_dictionary/power_properties.html。 - IVlad

多么令人难以置信且简单的解决方案！我已经苦苦挣扎了好几天，谢谢您先生。 - John Doe

@约翰·杜请注意，这种方法与对log(f)和log(g)的比较本质上相似。 - MBo

Answer 2

对两个函数同时进行以2为底的对数运算，我们得到 log(f(n)) = n，其中 log(g(n)) = (log(n))^2。

现在，(log(n))^2 = o(n)，而且log是一个单调递增的函数，因此我们有

g(n) = o(f(n))，也就是说，f(n)在n很大时增长得更快。

以下是另一种更严谨的证明方法：

令L = lim{n->inf} g(n) / f(n) = lim{n->inf} n^(log(n))/2^n。

因此，log(L) = lim{n->inf} log^2(n) - n

  ` = lim{n->inf} n*(log^2(n)/n) - 1)`

  ` = lim{n->inf} (n) * lim{n->inf} (log^2(n)/n) - 1)`

  ` = lim{n->inf} (n) * (0-1)`

  ` = lim{n->inf} (-n) = -inf`

=> L = 2 ^ (-inf) = 0

根据 o(n) 的另一种定义（小写字母 o，参见此处：https://en.wikipedia.org/wiki/Big_O_notation），

L = lim{n->inf} g(n) / f(n) = 0

=> g(n) = o(f(n))。

以下是原始数据和对数坐标下比较 f(n) 和 g(n) 增长的图表：

- Sandipan Dey

---

比较两个函数对数的增长率是否有效？ - John Doe

@JohnDoe 为什么不呢？两个函数的对数也是复合函数。基本上我们要看到的是，在对数尺度下，一个函数支配另一个函数的增长率，而对数是单调递增的函数，因此第一个函数在原来的定义域中也会支配第二个函数的增长。 - Sandipan Dey