这些函数中哪一个对无穷大有更高的增加？

Question

我想比较两个给定函数的渐近递增，看看哪个函数的递增更高。

给定函数f(n) = n*ln(n)和g(n)= $e^log_2(n)$，我的解决方案如下图所示：

结果是 n*ln(n) 更快。通过查看图表，我不相信。谁能告诉我如何解决这个问题？

Answer 1

您的图表说的是事实，g(n) 比 f(n) 增长得更快。原因如下：

关键等式如下

log_a(x) = log_b(x)/log_b(a)                         (*)

这很容易通过定义证明，因为

b^{log_a(x)log_b(a)} = (b^{log_b(a)})^{log_a(x)}     ; t^{sr} = (t^s)^r
                     = a^{log_a(x)}                  ; b^{log_b(a)}=a
                     = x.

（证明完整，但你可以两边取log_b进一步说服自己）

现在我们可以针对我们的特定情况使用 (*)：

log_2(n) = log_e(n)/log_e(2)                         (**)

并得到

g(n) = e^{log_2(n)}                                  ; def of g(n)
     = e^{log_e(n)/log_e(2)}                         ; (**)
     = (e^{log_e(n)})^{1/log_e(2)}                   ; t^{s/r} = {t^s}^{1/r}
     = n^{1/log_e(2)}                                ; e^{log_e(n)}=n
     = n^{log_2(e)}                                  ; (*) for x=b=e, a=2

但是由于e > 2，我们推断log_2(e) > 1，比如说log_2(e) = 1 + δ，δ > 0。于是

g(n) = n*n^δ

我们现在必须将 g(n) 与

进行比较

f(n) = n*ln(n)                                       ; def of f(n)

这与比较 n^δ 和 ln(n) 相同。为此我们可以计算

lim n^δ/ln(n)

与

相同

lim x^δ/ln x                                         ; x → ∞

我们可以在哪里使用 L'Hôpital 的规则

lim δx^{δ-1}/x^{-1} = lim δ x = δ lim x = ∞          ; δ > 0.

因此

lim g(n)/f(n) = ∞

和 g(n) 比 f(n) 增长得更快。

这些函数中哪一个对无穷大有更高的增加？

Which of these function has a higher increasing for infinity?

math

complexity-theory

function