quicksort n*log2(n)

[mikrop]

Hallo

Ich habe ein Problem. Ich habe ein array das mit zufalls zahlen gefüllt wird.

Nun hab ich den Algo von wikipedia für Quicksort genommen.

Quicksort ? Wikipedia

Nun zähle ich swaps bei jedem tausch und in den beiden inneren while schleichen zähle ich jeweil Ops.

Nun für 100 Elemente liege ich immer so um die 6XX was dem n*log2(n) von 100 mit 664 Ops entspricht.

Wenn ich nun aber auf 45000 Elemente gehe komme ich beim Programm plötzlich ständig in den Millinonen bereich, wobei aber der n*log2(n) bei 45000 nur 695593 sein dürfte als weniger als ein zehntel dessesn was ich zähle.

frage wo liegt mein Fehler etwa in meiner zählweise oder wie ich das ganze generell sehe mit dem log?

lg Mikrop

[lupo49]

In dem Artikel wird auch beschrieben, dass O(n*log(n)) nur für den besten und durchschnittlichen Fall gilt. Der Worst-Case wird hier mit O(n^2) angegeben.

[mikrop]

Hallo

also ja das stimmt, leider müsste für den Durchschnitt aber ja der wert mal unter oder nahe zu den 600k kommen ich bin aber ständig egal wie oft ich es probiere (srand(time(NULL))) immer im 8-9millionen Bereich.

Vielleicht liegts an meiner Flaschen deutung von O(n*log(n)) aber ich weiß nicht so recht.

lg Mikrop

[Klotzkopp]

Vielleicht liegts an meiner Flaschen deutung von O(n*log(n))

Ja.

Die O-Notation gibt eine asymptotische obere Schranke an, die mathematische Definition kannst du bei Wikipedia nachlesen.

Ganz grob gesagt bedeutet das nur, dass die Laufzeit von Quicksort im durchschnittlichen Fall "nur" um einen endlichen Faktor größer ist als n * log(n).

Das ist auch der Grund, warum der Logarithmus hier keine Basis hat, denn die würde sich nur als konstanter Faktor auswirken.