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
![](https://images.gutefrage.net/media/user/Rammstein53/1615404814643_nmmslarge__0_0_346_346_2e08198db203389692d6d8287572496d.png?v=1615404815000)
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)
![](https://images.gutefrage.net/media/default/user/10_nmmslarge.png?v=1551279448000)
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
![](https://images.gutefrage.net/media/user/Rammstein53/1615404814643_nmmslarge__0_0_346_346_2e08198db203389692d6d8287572496d.png?v=1615404815000)
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.
![](https://images.gutefrage.net/media/default/user/10_nmmslarge.png?v=1551279448000)
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
![](https://images.gutefrage.net/media/user/Rammstein53/1615404814643_nmmslarge__0_0_346_346_2e08198db203389692d6d8287572496d.png?v=1615404815000)
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.
![](https://images.gutefrage.net/media/default/user/10_nmmslarge.png?v=1551279448000)
![](https://images.gutefrage.net/media/default/user/10_nmmslarge.png?v=1551279448000)
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?