Quicksort: Best Case berechnen

[Dr. Solution]

Hallo zusammen

Ich hab mir in C++ einen Quicksort implementiert (ja ich weiss, STL. Wollte es einfach selbst schaffen...) Aus diversen Quellen weiss ich, dass sich der Best Case des Quicksort wie folgt berechnet:

O(n*log(n))

Wenn ich jetzt aber die Anzahl Schritte meines Quicksorts zähle, komme ich auf weniger

Entweder habe ich den ultimativen Sortieralgorithmus entdeckt, oder - wahrscheinlicher -mache ich einen Überlegungsfehler.

In meinem Beispiel handelt es sich um einen Array mit 14 Werten. Wende ich die Formel an, bekomme ich 14*log(14) = 16.04. Beobachte ich nun, was in meinem Algorithmus abläuft, sehe ich, dass dieser nur 10 Schritte benötigt:

4.29  8.84  2.98  7.32  8.79  2.19  3.95  4.55  9.38  9.81  2.99  3.14  0.55  2.19 

2.19  0.55  2.98  3.14  2.99  2.19  3.95  4.55  9.38  9.81  8.79  7.32  8.84  4.29 


2.19  0.55  2.98  3.14  2.99  2.19 

2.19  0.55  2.19  3.14  2.99  2.98 


2.19  0.55  2.19 

0.55  2.19  2.19 


2.19  2.19 

2.19  2.19 


3.14  2.99  2.98 

2.98  2.99  3.14 


4.55  9.38  9.81  8.79  7.32  8.84  4.29 

4.55  4.29  7.32  8.79  9.81  8.84  9.38 


4.55  4.29  7.32 

4.29  4.55  7.32 


4.55  7.32 

4.55  7.32 


9.81  8.84  9.38 

8.84  9.81  9.38 


9.81  9.38 

9.38  9.81 

Was mache / denke ich falsch? Vielen Dank für Eure Hilfe!

Marcel

[Klotzkopp]

Die O-Notation sagt nichts über die Anzahl der "Schritte" (Vertauschungen oder Vergleiche) aus. Das ist auch keine Formel, in die du für n irgendetwas einsetzen könntest.

[sØlk]

japp genau so ist es.

das n*log(n) ist nur eine größenordnung...

so wie O(n²) ... wie auch immer.

das heisst nicht, dass es genau die Laufzeitkomplexität hat, sondern, dass sie in der größenordnung von O(n*log(n)) liegt.

sØlk

[Dr. Solution]

Die O-Notation sagt nichts über die Anzahl der "Schritte" (Vertauschungen oder Vergleiche) aus. Das ist auch keine Formel, in die du für n irgendetwas einsetzen könntest.

Aha! Was sagt die Formel denn genau aus?

Mir geht es darum, in meiner Applikation während dem Sortieren einen Progress-Balken anzuzeigen. Dafür wäre es hilfreich, die Anzahl Sortierschritte ungefähr voraussagen zu können.

Danke und Gruss

[Klotzkopp]

Aha! Was sagt die Formel denn genau aus?

Sie sagt nur aus, wie sich der Algorithmus in Abhängigkeit von der Anzahl der Elemente verhält. Du könntest also bestenfalls die Zeit, die du für ein kleines Array brauchst, messen, und diesen Wert auf ein großes hochrechnen.

Mir geht es darum, in meiner Applikation während dem Sortieren einen Progress-Balken anzuzeigen. Dafür wäre es hilfreich, die Anzahl Sortierschritte ungefähr voraussagen zu können.

Das kannst du nicht, zumindest nicht, ohne ziemlich viel Zeit für eine Vorabanalyse zu verbraten, was sicher nicht in deinem Sinne ist. Wie wäre es damit: Immer, wenn du beim trivialen Fall angekommen bist, kennzeichnest du diesen Teil als "erledigt". Welcher Anteil das ist, kannst du ja anhand der bis dahin erfolgten Halbierungen ermitteln. Wenn du also z.B. nach 3 Halbierungen einen Trivialfall erledigt hast, hast du 1 / (2 hoch 3) = 1/8 = 12,5% erledigt.

[Dr. Solution]

Das ist auch keine Formel, in die du für n irgendetwas einsetzen könntest.

Sie sagt nur aus, wie sich der Algorithmus in Abhängigkeit von der Anzahl der Elemente verhält

Also kann ich doch für n die Anzahl Elemente einsetzen, oder?

[Klotzkopp]

Also kann ich doch für n die Anzahl Elemente einsetzen, oder?

Nein. Das ist keine Formel, sondern eine asymptotische obere Schranke.

Siehe auch:

http://de.wikipedia.org/wiki/Landau-Symbol

http://de.wikipedia.org/wiki/Komplexit%C3%A4tstheorie

[Rondario]

Aha! Was sagt die Formel denn genau aus?

Die Komplexitätsklasse sagt nur aus wie sich die Laufzeit der Funktion für große n (n gegen unendlich) verhält. Hierbei fallen sämtliche Additiven wie Multiplikativen Konstanten raus. Wenn Algorithmus A also immer 1000 mal so lange braucht wie Algorithmus B, dann liegen beide in der selben Laufzeitklasse, da 1000 eine von der Eingabegröße unabhängige Konstante ist. Das ganze sagt nur aus, dass für große n die Laufzeit eben in etwa linear sein wird, oder in etwa quadratisch, oder was auch immer.

[Toupman]

Ah, das find ich doch mal klasse, das hier wenigstens auch mal ein bisschen Niveau drinne steckt. Ich war so entäuscht als ich in der BS unseren Klassenlehrer(FIAE) gefragt habe ob wir auch O-Notation machen und der nur unwissend den Kopf geschüttelt hat.

[Guybrush Threepwood]

Naja aber ich kann ja schon einen Wert für n einsetzten. Denn die Geschwindigkeit eines Sortieralgoritmus ist ja abhängig von der Anzahl der zu sortieren Elemente n und die Notation O(n²) (wie sie z.B. durchschnittlich beim Bubblesort erreicht wird) bedeutet ja nichts anderes als das der Sortieraufwand quadratisch mit der Anzahl der Elemente ansteigt.

Wenn ich jetzt nicht so der Mathe Crack bin und mir O(n*log(n)) nichts sagt könte ich ja bei beiden Notationen einen Wert einsetzten um zu sehen welcher Algorithmus der schnellere wäre. Aber wenn ich das richtig verstanden habe kann man die beiden Ergebnisse nicht miteinander Vergleichen um z.B. einen Faktor zu berechnen um wieviel der eine jetzt schneller wäre als der andere.

Außerdem habe ich gelesen das die O-Notation nicht 100% genau ist, sondern nur eine ungefähre Aussage auf die Geschwindigkeit trifft. D.h. 2 Algorithmen die nach Notation gleich schnell sind, müssen das nicht in Wirklichkeit sein.

[Toupman]

Leider simmt deine Überlegung nicht wirklich, weil die O-Notation nur eine Kategorisierung erlaubt. O(n*log(n)) bedeutet nur das QuickSort in dieser Kategorie liegt. Du weißt aber nicht welcher ganzzahlige Faktor noch zur wirklichen Anzahl der Schritte fehlt. D.h. du kannst auch nicht mit einem anderen Algorithmus vergleichen, weil du auch dessen Faktor nicht kennst.

P.S.: Also selbst nach Mathe Grundkurs, sollte man wissen das n* log(n) < n².

[Guybrush Threepwood]

Ich habe ja nicht gesagt das man so die Anzahl der Schritte ausrechnen kann, nur das man durchaus die Anzahl der Elemente für n einsetzten kann um die Formel aufzulösen. n* log(n) und n² war dabei natürlich nur ein einfaches Beispiel.

[Klotzkopp]

Wenn ich jetzt nicht so der Mathe Crack bin und mir O(n*log(n)) nichts sagt könte ich ja bei beiden Notationen einen Wert einsetzten um zu sehen welcher Algorithmus der schnellere wäre. Aber wenn ich das richtig verstanden habe kann man die beiden Ergebnisse nicht miteinander Vergleichen um z.B. einen Faktor zu berechnen um wieviel der eine jetzt schneller wäre als der andere.

Wenn du die Werte nicht vergleichen kannst, kannst du auch nicht ermitteln, welcher Algorithmus schneller ist. Das geht mit Komplexitätsklassen schlicht und einfach nicht. Das sind Grenzwertbetrachtungen, es ergibt einfach keinen Sinn, dort Werte einzusetzen.

Außerdem habe ich gelesen das die O-Notation nicht 100% genau ist, sondern nur eine ungefähre Aussage auf die Geschwindigkeit trifft. D.h. 2 Algorithmen die nach Notation gleich schnell sind, müssen das nicht in Wirklichkeit sein.

Und hier schließt sich der Kreis. Die Komplexitätsklassen sind eben keine Formeln für die Geschwindigkeit eines Algorithmus. Wenn du sie trotzdem als solche benutzt, ist es klar, dass die "Ergebnisse" nicht genau sind. Sie geben asymptotische obere Schranken an. Das bedeutet hier nicht mehr, als dass n * log n für hinreichend große n immer mindestens so schnell wächst wie das Zeitverhalten des Best Case bei Quicksort.

[Guybrush Threepwood]

hmm ok

[Gast runtimeterror]

Aha! Was sagt die Formel denn genau aus?

Mir geht es darum, in meiner Applikation während dem Sortieren einen Progress-Balken anzuzeigen. Dafür wäre es hilfreich, die Anzahl Sortierschritte ungefähr voraussagen zu können.

Um noch mal meinen Senf dazuzugeben:

Progress-Bar ist theor. kein Problem: Der Quick-Sort-Algorithmus verwendet bekanntermaßen ja eine Rekursion. Die Anzahl der aufgerufenen return-Statements darin sollte sich proportional zur Größe des zu sortierenden Arrays verhalten. Zu Deutsch: Sortier mal eine Liste mit 1000 Einträgen und lass dir die return-Aufrufe zählen. Je nach Implementierung steht der Tacho dann bei ca 500, 1000, 2000, 3000, o.Ä. Daraus eine Fortschrittsbalken zu machen sollte nicht so das Thema sein. Der Fortschrittsbalken wird dir allerdings nicht zwingend eine brauchbare Auskunft über den zeitlichen Verlauf der Sortierung geben.

Die Ordnungsangabe eines Algorithmus ist ein asymptotischer Wert (bei großem n), der proportional ist zu der Anzahl der durchzuführenden Arbeitschritte. Der Quicksort-Algorithmus benötigt im MITTEL n*ld(n) (ld = logarithmus dualis = log(n) / log(2)) - daher kann dein Verfahren auch gerne mal was weniger brauchen

In einigen Fällen ist auch der Heap-Sort schneller, da dieser eine Laufzeit von n*ld(n) garantiert.

[Klotzkopp]

Der Quicksort-Algorithmus benötigt im MITTEL n*ld(n) (ld = logarithmus dualis = log(n) / log(2))

Gerade weil die Komplexitätsklassen einen proportionales Verhalten wiedergeben, ist es egal, welche Basis der Logarithmus hat. Eine andere Basis bewirkt nur eine Änderung des konstanten Faktors, der ja sowieso wegfällt.

[Gast runtimeterror]

Jetzt wo du's sagst... stimmt

kleine Korrektur

ld(n) = log(n) / log(10)

lb(n) = log(n) / log(2)

... nur damit mich hier keiner für irgendwelche abstürzende Flugzeuge haftbar macht.