Big O Notation von Funktionen berechnen?
Ich soll die Big O Notation von folgenden Funktionen beweisen:
Ist O(x):
Element von O(ln n) Ist O (n^2)
Für mich macht das das erste und das 3. keinen Sinn, da n*ln(n) ja nicht quadratisch ist, sondern logarithmisch. Und das erste hat ja einen Wurzel Faktor in sich.
Wie gehe ich da vor? Habe ich einen Denkfehler?
2 Antworten
Eine Funktion f(x) ist Element von O( g(x) ), wenn für x --> unendlich gilt :
f(x) <= const * g(x)
Beispiele
f(x) = 23x + 2sqrt(x) <= 23x + 2x <= 25x, daraus folgt f(x) € O(x)
f(n) = n * ln(n) <= n*n für n >= 1, daraus folgt f(n) € O(n^2)
Das erste weiß ich alles durch x und dann läuft das nicht mehr gegen unendlich, richtig?
Beim letzten komme ich nicht ganz drauf.
Würde:
f(n) = (n* ln(n)) / n^2 = n/n^2 * (ln(n) /n^2)=> n* (ln(n)/n^2)
Wie man nun ln(n) / n^2 auflöst, dass man dann auf n*n kommt weiß ich nicht
Bei der O-Notation geht es nur um grobe Abschätzungen, also
sqrt(x) < x, für x > 1
oder
ln(n) < n für n > 1
Grobe Abschätzungen deshalb, weil man sich schnell einen Überblick über z.B. Laufzeiten eines Programms oder einer mathematischen Restgrösse verschaffen will. Deshalb gilt z.B.
n*ln(n) € O(n^2)
Man könnte zwar genauso gut behaupten:
n*ln(n) € O( n*l(n) )
aber das ist weniger anschaulich.
Also wenn die Differenz der beiden Notationen gegen unendlich auf unendlich anwächst, dann sind sie nicht gleich? Also Expondentiell entfernt sich ja unendlich weit von linear
Eine Funktion f(x) ist Element von O( g(x) ), wenn für x --> unendlich gilt :
f(x) <= const * g(x)
In den meisten Fällen gilt nur
f(x) < const * g(x)
und es spielt keine Rolle, wie gross die Differenz (f(x) - const * g(x)) für x -> unendlich wird.
Wir haben gelernt, dass man nur den am stärksten wachsenden Term berücksichtigt, oben also 23x und Konstanten ebenfalls weglässt, aber gilt oben O(23x+2sqrt(x)=O(23x)=O(x)
n*log n (quickster) < n*n (bubblesort) und wird daher von n*n dominiert
Wie kommst du auf 23x+2x?
Und bei f(n) wie genau hast du das ln rausbekommen?