Was bedeutet der Ausdruck O(n*log(n)) - Informatik?
Hey liebe Gute Frage Community,
ich bin gerade dabei mir das Thema Sortierverfahren und deren Komplexität genauer anzuschauen. Ich treffe immer wieder auf den in der Frage genannten Ausdruck O(n*log(n)). Kann mir vielleicht jemand erklären, was die einzelnen Bestandteile aussagen? Soviel hab ich selber schon herausgefunden, n beschreibt die Anzahl von Elementen im zu sortierenden Array. O ist ein Landau Ausdruck (Bitte nochmal erklären, hab noch nicht so ganz den Sinn verstanden). Log(x) ist sozusagen eine umgedrehte Exponentialfunktion, aber ich hab noch nicht so ganz verstanden, was das Ergebnis ist. Die Funktion beschreibt doch einen Graphen. Aber eigentlich brauche ich doch ein eindeutig definiertes Ergebnis, oder irre ich mich?
Vielen Dank für Eure Hilfe, ich würde mich über ausführliche Erklärung unglaublich freuen und Website Verweise wären top, wenn ich mal etwas zitieren muss. Danke!!
3 Antworten
Kennt man unter https://de.wikipedia.org/wiki/Landau-Symbole
O(n log(n)) sagt aus, dass der Algorithmus durch "n*log(n)" nach oben beschränkt wird.
Oder formaler: f = O(n log(n)), die Funktion f wächst nicht schneller als n*log(n).
Dadurch kann man Laufzeiten (in Schritten) von Algorithmen nach oben abschätzen/beschränken.
So kann man zum Beispiel die Laufzeiten (in Schritten) von verschieden Sortieralgorithmen vergleichen. O(n^2) ist dabei eine schlechtere Laufzeit (in Schritten) als O(n*log(n)). Dabei ist allerdings noch zu vergleichen wie die Algorithmen im worst case, best case und average case abschneiden.
Gruß
Aso, log steht für https://de.wikipedia.org/wiki/Logarithmus
Im Zweifel benutzt Du einen Taschenrechner, ja.
Aber im Falle von landauschen Symbolen hast Du es eh nur mit einer Größe n zutun und keine festen Werte.
Gruß
Konkrete Werte benötigst Du in der Regel nicht. Du weißt z.B. , daß n log n < n^2 ist. Letztlich geht es um die Bewertung der Geschwindigkeit, egal wie groß n (also die Eingabemenge) ist.
Man kann das aber auch exemplarisch machen: Nehmen wir an, wir haben rund 1.000 zu sortierende Elemente, ein Algorithmus mit Laufzeit n^2 benötigt 1.000.000 Schritte, wobei jeder dieser Schritte aus einer konstanten Anzahl an Operationen besteht. Ein Algorithmus, der n log n benötigt, liegt bei 10.000 Schritten. Nehmen wir 65.000 Elemente, dann stehen 4 Mrd Schritte bei n^2, etwa 1 Mio Schritte bei n log n gegenüber.
Auch wenn man sich bei der Betrachtung eigentlich nicht für so kleine Eingaben interessiert, ich denke der Sinn dahinter dürfte an den Beispielen klar werden.
Ein Schmankerl zum Abschluß: Bei 16,5 Mio zu sortierenden Elementen stehen 2,7*10^14 (n^2) ungefähr 4*10^8 (n log n) gegenüber. Da fängt es dann an richtig schmerzhaft zu werden :-D.
Wenn ich 1000*Log(1000) in den Taschenrechner eingebe, kommt 3000 raus, mache ich was falsch?
Es ist der Logarithmus zur Basis 2. Man schreibt das nicht immer dazu (aus Faulheit), weil bei binären Zahlen die Basis eben die 2 ist. Wenn wir bei Sortierverfahren bleiben, hier wird in der Regel partitioniert (in 2 Partitionen). Dadurch komme ich dann auf 2^x=n, mit n=Eingabemenge und x tiefe der Rekursion. x=log_2(n) und in jeder Rekursionsebene sind es n zu behandelnde Elemente, woraus sich die Größenordnung n * log_2(n) ergibt.
Okay hab's verstanden, aber wie kommst du denn auf die Werte 2,7*10^14?
Der Wert ist gerundet. Es ging um die Gegenüberstellung der Größenordnungen.
Gerade in der Oberstufe 12/2?
Du hast ja ein zu sortierendes Array mit n Elementen. O gibt dabei den nötigen Laufzeitaufwand in Abhangigkeit von n, also in Abhangigkeit von der Anzahl an zu rotierenden Elementen an. Laufzeitaufwand bedeutet einfach, wie viele Berechnungen oder Vergleiche dazu durch geführt werden müssen. Dementsprechend entsteht Rechenaufwand und das braucht Zeit.
Umso größer n, also dein Array, ist, umso länger dauert das Sortieren natürlich. Und wie schnell der Rechenaufwand zum Sortieren steigt, wenn n größer wird, gibt die Funktion O(n*log(n)) an.
Es gibt Sortieralgorithmen, bei denen der Laufzeitaufwand exponentiell steigt. D.h. wenn n größer wird, wird die Laufzeit gleich viel länger, weil Exponentialfunktionen eben sehr schnell in die Höhe schießen. Stell Dir dazu einfacb den Graphen vor.
In dem Fall n*log(n) hast du einmal n, das würde einfache ein Laufzeitaufwand bedeuten, der direkt proportion zur Arraygröße wächst. Und du hast zusätzlich den Logarithmus, der aber ja im Unendlichen nur noch sehr langsam steigt. Heißt der Laufzeitaufwand deines Algorithmus steigt bei weitem langsamer als z.B. einer mit O(2^n), wenn dein Array größer wird.
Ist die beschreibung davon die ich grade auf stackoverflow gefunden habe :
"A quicksort touches every single element, a small number of times. If there's a billion elements, the quick sort touches all of them, about 30 times: about 30 billion touches total."
Quelle: https://stackoverflow.com/questions/42238323/how-is-on-log-n-different-then-olog-n
(Ich bin mir aber sehr unsicher ob es dir was bringt)
Merge Sort, Best Case - Eigentlich aber allgemein, was sagt mir dieser Ausdruck.
https://stackoverflow.com/questions/7801861/why-is-merge-sort-worst-case-run-time-o-n-log-n
da bringt einer ein beispiel code für merge sort und kommt durch irgendeine schlussfolgerung (habs nur überflogen ) dazu das dieser code das gleiche wie deine gleichung bedeutet
Danke, aber wie ich aus dem Ausdruck Log(2) nun ein Ergebnis ziehen? Muss ich einen Taschenrechner nutzen, oder wie geht das?