Laufzeit Quicksort

Neue Frage »

isy Auf diesen Beitrag antworten »
Laufzeit Quicksort
Hallo, ich muss etwas über die Laufzeit von Quciksort schreiben.

Nun treten bei mir anscheinend generelle Probleme auf...

Als Maß für die Laufzeit wird ja die Gesamtanzahl der benötigten Vergleiche betrachtet...
Im worst case sind das (n-1)+(n-2)+(n-3)+...+1 = n*(n-1)/2 Vergleiche. Soweit klar...
Warum beträgt dann aber im worst case die Laufzeit O(n^2)???

Ich habe wahrscheinlich ein grundlegendes Problem mit der Notation O...

Kann mir das wohl jemand erklären???

Danke und Gruß
AD Auf diesen Beitrag antworten »

Dann informiere dich doch mal über die Landau-Symbole:

So bedeutet , dass es ein und gibt mit

für alle ,

oder anders formuliert: Dass der Quotient beschränkt bleibt.



Im vorliegenden Fall ist und , der Quotient



ist dann auch beschränkt, somit ist die Aussage gerechtfertigt.
 
 
isy Auf diesen Beitrag antworten »

Danke!!!!
Kappiert Big Laugh
isy Auf diesen Beitrag antworten »
noch eine Frage LZ Quicksort
Hallo,

wenn ich die Laufzeit von Quicksort im worst case damit begründe, dass Quicksort
(n-1)+(n-2)+...+1 = n*(n-1)/2 Vergleiche benötigt und daraus folgt O(n²) wie kann ich dann auf Grundlage der benötigten Vergleiche begründen, dass Quicksort im "best case" eine LZ von O(n*log n) hat?

Gruß und Danke schon mal!
Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »