Quicksort Algowiki

Bei Postings zu Aufgabe Nr. x auf Blatt Nr. y lassen Sie Ihr Betreff bitte mit "y.x: " beginnen, gefolgt von einer möglichst präzisen Überschrift, danke!

Moderator: Algorithmen und Datenstrukturen

Forumsregeln
Bei Postings zu Aufgabe Nr. x auf Blatt Nr. y lassen Sie Ihr Betreff bitte mit "y.x: " beginnen, gefolgt von einer möglichst präzisen Überschrift, danke!
Benutzeravatar
Malou
Windoof-User
Windoof-User
Beiträge: 26
Registriert: 19. Jun 2016 17:54

Quicksort Algowiki

Beitrag von Malou » 19. Jun 2016 18:02

Hallo allerseits,

Ich habe mich gerade mit der Komplexitätsklasse des Algorithmus Quicksort auseinandergesetzt und denke, einen kleinen Fehler auf dem Algowiki gesehen zu haben.
Im Beweis wird erklärt, wie schnell der Algorithmus im Besten Fall wächst. Danach sollte wahrscheinlich gezeigt werden, wie es im schlimmsten Fall wächst, wird aber widerum gesagt, dass der besten Fall betrachtet wird:

Anstatt "the total complexity is O(T*n*log(n)) in the worst case" sollte "[...] in the best case" geschrieben werden.

Oder habe ich was falsch verstanden?

Grüsse,

Malou

Prof. Karsten Weihe
Moderator
Moderator
Beiträge: 1824
Registriert: 21. Feb 2005 16:33

Re: Quicksort Algowiki

Beitrag von Prof. Karsten Weihe » 19. Jun 2016 22:13

mo26loba hat geschrieben: Im Beweis wird erklärt, wie schnell der Algorithmus im Besten Fall wächst.
Ich finde den String "best" nur einmal auf der Seite, nämlich in der Bildunterschrift, wo die verschiedenen Fälle nur skizzenhaft illustriert werden. Wo finden Sie etwas zum Best Case :?:
mo26loba hat geschrieben: Anstatt "the total complexity is O(T*n*log(n)) in the worst case" sollte "[...] in the best case" geschrieben werden.
Sie zitieren aus dem Beweis. Ich nehme an, Sie zweifeln damit den zweiten Satz von Complexity / Statement an? Das ist durchaus der Worst Case, nicht der Best Case :!: :shock:

Folgendes: Der erste Satz von Complexity / Statement sagt, egal wie die Strategie zur Pivotwertwahl aussieht, kann die Anzahl Vergleiche für Sequenzen der Länge \(n\) asymptotisch nicht schlechter als \(n^2\) sein. Mit anderen Worten: Wir wählen eine beliebige, aber feste Strategie zur Wahl des Pivotwerts. Wenn man nun für jede Zahl \(n\) die Eingabesequenz hernimmt, bei der Quicksort mit dieser Strategie die höchste Anzahl Vergleiche benötigt, dann wächst diese Anzahl keinesfalls schneller als quadratisch in \(n\).

Wenn wir uns nur bestimmte Strategien zur Wahl des Pivotwerts ansehen, dann können wir eine bessere Abschätzung nach oben im Worst Case angeben. Das ist der Inhalt des zweiten Satzes von Complexity / Statement. Genauer gesagt, geht es um Strategien, die jede Sequenz garantiert so zerlegen, dass jede der beiden rekursiv zu behandelnden Teilsequenzen nicht mehr als einen bestimmten, vorgegebenen Bruchteil der Sequenz umfassen. Bei jeder solchen Strategie kann man den Worst Case nicht nur mit \(n^2\) asymptotisch nach oben abschätzen, sondern es geht sogar mit \(n\log n\).

Klarer geworden?

KW

Benutzeravatar
Malou
Windoof-User
Windoof-User
Beiträge: 26
Registriert: 19. Jun 2016 17:54

Re: Quicksort Algowiki

Beitrag von Malou » 21. Jun 2016 13:06

Prof. Karsten Weihe hat geschrieben:
mo26loba hat geschrieben: Im Beweis wird erklärt, wie schnell der Algorithmus im Besten Fall wächst.
Ich finde den String "best" nur einmal auf der Seite, nämlich in der Bildunterschrift, wo die verschiedenen Fälle nur skizzenhaft illustriert werden. Wo finden Sie etwas zum Best Case :?:
Ich wollte hier "im schlimmsten Fall" sagen, falsch getippt.
Prof. Karsten Weihe hat geschrieben:Klarer geworden?
Jetzt habe ich es verstanden, vielen Dank für die ausführliche Antwort!
:D

Malou

Antworten

Zurück zu „AuD: Theoretische Aufgaben“