Ich muss die Wachstumsrate der folgenden Funktionen vergleichen:Vergleichen Sie die Wachstumsrate von zwei Funktionen. (Tricky)
f (n) = 2^n und g (n) = n^log (n) (wenn n positive Unendlichkeit nähert).
Ist das überhaupt möglich?
Let n = 2^k. Wir haben:
2^n = 2^(2^k)
n^log(n) = (2^k)^log(2^k) = (2^k)^(k log 2)
= 2^(k^2 log 2)
vergleichen Jetzt 2^k-k^2 log 2. Dies ist ein grundlegender Vergleich: 2^k ist größer für alle groß genug k.
Unter log (Basis 2) für beide Funktionen erhalten wir log(f(n)) = n wo log(g(n)) = (log(n))^2. Jetzt
, (log(n))^2 = o(n) und log eine monoton steigende Funktion ist, haben wir
g(n) = o(f(n)), das heißt f(n) für große Werte von n viel schneller wächst.
Dies ist ein weiterer Weg, um es zu beweisen rigorosen:
L = lim{n->inf} g(n)/f(n) = lim{n->inf} n^(log(n))/2^n lassen.
Daher 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
Gemäß der alternativen Definition von o(n) (small o, siehe hier: https://en.wikipedia.org/wiki/Big_O_notation),
L = lim{n->inf} g(n)/f(n) = 0
=> g(n) = o(f(n)).
Hier sind die Zahlen f(n) und g(n) Wachstum im Original und in Log-Skala Vergleich:
Ist es gültig, um die Wachstumsrate der Logarithmen von zwei Funktionen zu vergleichen? –
@JohnDoe warum nicht? Logarithmen von zwei Funktionen sind auch (zusammengesetzte) Funktionen. Grundsätzlich sollten wir hier sehen, dass eine Funktion die Wachstumsrate des anderen im logarithmischen Maßstab dominiert und Log eine monoton ansteigende Funktion ist, daher wird der erste auch das Wachstum des anderen im ursprünglichen Bereich dominieren. –
Wow das ist ein interessanter Ansatz. Es gibt eine Sache, die ich nicht verstehe, wie ist das passiert? (2^k)^(k log 2) = 2^(k^2 log 2) –
@JohnDoe ist nur die Eigenschaft "Power to a power": '(a^x)^y = a^(x * y) '. Sehen Sie hier zum Beispiel: http://www.icoachmath.com/math_dictionary/power_properties.html – IVlad
Was für eine unglaubliche und einfache Lösung! Ich habe seit Tagen gekämpft, danke, mein Herr. –