f (n) = log (n)^m ist O (n) für alle natürlichen Zahlen m?

Question

Ein TA hat mir gesagt, dass das heute wahr ist, aber ich konnte das nicht durch googlen verifizieren. Das heißt, Funktionen wie log (n)^2, log (n)^3, ..., log (n)^m sind alle O (n).

Ist das wahr?

Answer 1

Anspruch

Die Funktion f(n) = log(n)^m, für jede natürliche Zahl m > 2 (m ∈ ℕ+) in O(n).

I.e. gibt es eine Reihe von positiven Konstanten c und n0 so dass folgendes gilt:

log(n)^m < c · n, for all n > n0, { m > 2 | m ∈ ℕ+ }  (+) 

---

Proof

• Angenommen, (+) tut nicht halten, und Bezeichnen Sie diese Annahme als (*).

Das heißt, da (*), gibt es keine Reihe von positiven Konstanten c und n0 so dass (+) für jeden Wert von m > 2 hält. Unter dieser Annahme gilt die folgende, dass für alle positiven Konstanten c und n0, ein n > n0 so dass (dank @Oriol) existiert: Jetzt

log(n)^m ≥ c · n, { m > 2 | m ∈ ℕ+ }      (++) 

, wenn (++) hält, dann ist die Ungleichheit in (++) wird halten Sie auch, nachdem Sie eine monoton steigende Funktion auf beide Seiten der Ungleichung angewendet haben. Eine solche Funktion ist bequem, die log Funktion selbst

daher unter der Annahme, dass (++) hält, dann für alle positiven Konstanten c und n0 besteht ein n > n0 so dass gilt

log(log(n)^m) ≥ log(c · n), { m > 2 | m ∈ ℕ+ } 

m · log(log(n)) ≥ log(c · n), { m > 2 | m ∈ ℕ+ }   (+++) 

jedoch (+++) ist natürlich ein Widerspruch: da log(n) vorherrscht (wRT Wachstum) über log(log(n)),

wir dosen für jeden gegebenen Wert von m > 2 somit sehr passgenau finden eine Reihe von Konstanten c und n0 so dass (+++) (und damit (++)) für alle n > n0 verletzt wird.

Daher ist die Annahme (*) durch Widerspruch widerlegt, und daher gilt (+).

=> für f(n) = log(n)^m für jede endliche ganzzahlige m > 2 gilt, dass f ∈ O(n).

Answer 2

Ja. Wenn die Funktion f(n) ist, bedeutet dies m ist ein Parameter und f hängt nicht davon ab. In der Tat haben wir eine andere f_m Funktion für jede m.

f_m(n) = log(n)^m 

Dann ist es einfach. Angesichts m ∈ ℕ verwenden L'Hôpital's rule repeatively

 f_m(n)   log(n)^m   m * log(n)^(m-1) 
limsup ──────── = limsup ────────── = limsup ────────────────── = 
n→∞  n  n→∞  n   n→∞   n 

      m*(m-1) * log(n)^(m-2)    m! 
= limsup ──────────────────────── = … = limsup ──── = 0 
       n      n→∞ n 

Daher f_m ∈ O(n).

Natürlich wäre es anders, wenn wir f(m,n) = log(n)^m hätten. Zum Beispiel nehmen m=n,

 f(n,n)   log(n)^n 
limsup ──────── = limsup ────────── = ∞ 
n→∞  n  n→∞  n 

Dann f ∉ O(n)

Answer 3

In vielerlei Hinsicht ist es intuitiver ist, dass für jede positive ganze Zahl m haben wir:

x^m = O(e^x) 

Diese besagt, dass exponentielles Wachstum dominiert Polynom Wachstum (Deshalb sind exponentielle Zeitalgorithmen schlechte Nachrichten in der Computerprogrammierung).

Unter der Annahme, dass dies wahr ist, nehmen Sie einfach x = log(n) und nutzt die Tatsache, dass dann x gegen unendlich geht, wenn und nur wenn n gegen unendlich geht und dass e^x und log(x) sind Umkehrungen:

log(n)^m = O(e^log(n)) = O(n) 

Schließlich, da für jede natürliche Zahl m, die Wurzelfunktion n => n^(1/m) zunimmt, können wir das Ergebnis als

log(n) = O(n^(1/m)) 

umzuschreiben seine Art zu schreiben, sagt, dass log(n) langsamer wächst als jede Wurzel (Quadrat, Würfel, etc.) von n, die offensichtlich e^n schneller wächst als jede Leistung von n.

---

Auf Edit: zeigte die obige dass log(n)^m = O(n) aus dem bekannteren x^m = O(e^x) gefolgt. Um es zu einem in sich geschlossenen Beweis zu konvertieren, können wir das später etwas direkt zeigen.

Beginnen Sie mit der Taylor-Reihe für e^x:

e^x = 1 + x/1! + x^2/2! + x^3/3! + ... + x^n/n! + ... 

Dies ist bekannt x für alle reellen Zahlen konvergieren. Wenn eine positive ganze Zahl m gegeben ist, lassen Sie K = (m+1)!.Wenn dann x > K wir haben 1/x < 1/(m+1)!, daher

x^m = x^(m+1)/x < x^(m+1)/(m+1)! < e^x 

die x^m = O(e^x) impliziert. (Die letzte Ungleichheit in der oben gilt, da alle Glieder in der Entwicklung für e^x sind streng positiv, wenn x>0 und x^(m+1)/(m+1)! nur eines dieser Begriffe ist.)