warum n*log2(n)

[Odi1981]

Kann mir einer erklären warum der Merge Sort und Quick Sort Algorithmus

im durchschnitt n*log2(n) Schritte (Zeit) benötigt

Danke Odi

[rubbishbin]

Quicksort (siehe Kapitel 2.6)

Im besten Fall wird immer das mittlere Element als Pivot-Elemtent gewählt. Insgesamt gibt es dann ln(n) Stufen. Wobei im schlechtesten Fall n Stufen entstehen würden, da ja quasi jedes Element einmal zum Pivot-Elemtent werden würde.

Pro Stufe sind immer n Vergleiche nötig (nämlich jedes Element mit seinem Pivot-Element), womit man im besten Fall auf n*ln(n) Vergleiche kommt. Am besten lässt sich das durch einen Binärbaum darstellen (wie auch in dem oben genannten Link).

//Edit: Hab's eben nochmal überarbeitet. War vorher etwas unglücklich formuliert.

Bearbeitet 7. Januar 2009 von rubbishbin

[Odi1981]

Okay, aber habe ich nicht sowieso n bzw. (n-1) vergleiche egal ob das pivot element in der mitte oder z.b ganz links ist ?? Oder was ist ein vergleich ??

den ich muss ja jede zahl ansehen und sie links bzw. rechts des pivot elements einordnen

Also würde sich meines erachtens nur bei einer schlechten Pivotelement wahl log2(n) ändern und schlechet sprich höher werden weil keine optimale Auteilung erfolgt, und somit mehr ebenen für die Sorierung nötig werden

[rubbishbin]

den ich muss ja jede zahl ansehen und sie links bzw. rechts des pivot elements einordnen

Ganz genau! So kommen die ca. n Vergleiche zu Stande.

Also würde sich meines erachtens nur bei einer schlechten Pivotelement wahl log2(n) ändern und schlechet sprich höher werden weil keine optimale Auteilung erfolgt, und somit mehr ebenen für die Sorierung nötig werden

Auch richtig!

Nehmen wir an du hast folgende Zahlen zu sortieren und du nimmst immer das letzte Element, als Pivot-Element (PE):

1 2 3 4 5 6 7

Dann wird immer das größte Element der Teilmenge zum PE. Dann kommst du auf insgesamt n-1 (in dem Fall 6) Stufen. Anders wäre es bei folgender Menge:

1 3 2 5 7 6 4

Hier wird die Menge immer schön gleichmäßig in zwei gleich große Teilmengen unterteilt. Also ist die Menge nach ca. ln(n) Stufen sortiert (in dem Beispiel nach 2).

Bitte korrigier mich falls du (ihr) Fehler findet. Ich habe das auch gerade erst gelernt.

[Odi1981]

Ist die Lauftzeit des Quick Sort Algos n log(n) oder n log2(n)

n log2(n) oder ??? da ja ja bei jeder ebene eine Zweiteilung erfolgt ?!

[rubbishbin]

Logarithmus n zur Basis 2 kann man so:

log2(n)

oder so:

ln(n)

schreiben. IMHO.

[Klotzkopp]

Ist die Lauftzeit des Quick Sort Algos n log(n) oder n log2(n)

Im Durchschnitt ist n * log(n) eine asymptotische obere Schranke. Die Basis des Logarithmus ist hier egal, weil sie nur einen konstanten Faktor ausmacht, darum lässt man sie bei der O-Notation weg.

Logarithmus n zur Basis 2 kann man so:

log2(n)

oder so:

ln(n)

schreiben. IMHO.

Nein, ln ist der natürliche Logarithmus, also der Logarithmus zu Basis e.