2つの関数の成長率を比較します。 （トリッキー）

Question

次の関数の成長率を比較する必要があります。nが正の無限大に近づくと、f（n）= 2^nとg（n）= n^log（n）です。

これも可能ですか？

Answer 1

let 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) 

今k^2 log 2に2^kを比較します。これは基本的な比較です：2^kは十分に大きいすべてのために大きいですk。

Answer 2

log（基底2）を両方の関数に対して取ると、log(f(n)) = nはlog(g(n)) = (log(n))^2となります。

さて、(log(n))^2 = o(n)とlogは、単調増加関数である、我々はすなわち、f(n)がnの値が大きいため非常に速く成長し、

g(n) = o(f(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)成長を比較する数値は、次のとおり