比較兩個函數的增長率。（Tricky）

f（n）= 2^n和g（n）= n^log（n）（當n接近正無窮大時）。

這甚至可能嗎？

2017-03-12 John Doe

讓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。這是一個基本的比較：2^k是足夠大所有足夠大k。

來源

2017-03-12 18:56:29 IVlad

哇，這是一個有趣的方法。有一件事我不能忍受，這是怎麼發生的？（2^k）^（k log 2）= 2 ^（k^2 log 2） –

@JohnDoe它只是「權力的力量」財產：'（a^x）^ y = a ^（x * y ）'。看到這裏例如：http://www.icoachmath.com/math_dictionary/power_properties.html – IVlad

多麼令人難以置信和簡單的解決方案！我一直在苦苦掙扎，謝謝你，先生。 –

以log（基數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)增長：

來源

2017-03-12 19:40:40

比較兩個函數的對數增長率是否有效？ –

@JohnDoe爲什麼不呢？兩個函數的對數也是（複合）函數。基本上我們在這裏應該看到的是，一個函數在對數尺度上支配另一個函數的增長率，而log是單調遞增函數，因此第一個函數也將主導第二個在原始域中的增長。 –

比較兩個函數的增長率。 （Tricky）

回答

相關問題

比較兩個函數的增長率。（Tricky）