时间戳

首页 > 解决方案 > 这些函数中哪一个具有更高的无穷大？

function - 这些函数中哪一个具有更高的无穷大？

问题描述

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

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

在此处输入图像描述

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

标签： functionmathcomplexity-theory

解决方案

你的图表说的是实话，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).

推荐阅读