ich habe mehr eine Verständnisfrage zur Laufzeit von Quicksort.
Die Laufzeit im Durchschnitt beträgt ja O(n log n).
Quicksort benötigt doch O(n) für die Divide-Schritte und O(log n) zur Darstellung der Rekursionstiefe.
In einem Prüfungsprotokoll erwähnte ein Prüfling das Quicksort im worst case statt O(log n) Divide-Schritte O(n) Divide-Schritte benötigt.
Dies dürfte aber meines erachtens falsch sein, da doch die Anzahl der Divide-Schritte immer gleich ist.
Vielen Dank im Voraus.
Comments
chris*
Contributions on this page: 2
View profileWenn bei jedem Divide nur ein Element abgespalten wird (= Worst Case), sind das doch O(n) Divide-Schritte.
ikarusifly
Contributions on this page: 2
View profilemir ist klar, daß es im worst case O(n) Divide-Schritte sind.
Aber im Durchschnitt sind es doch auch O(n) Divide-Schritte, denn die Teilmengen werden doch so lange geteilt, bis schließlich Teilmengen entstehen, welche nur noch aus einem Element bestehen, Oder?
Es ist doch die Rekursionstiefe (sprich Rekursionsschritte), welche im Durchschnitt O(log n) und im worst case O(n) beträgt, Oder?
Aus diesen beiden Komponenten setzt sich doch die Laufzeit von Quicksort zusammen, also beträgt die durchschnittliche Laufzeit O(n log n),
da O(n) Divide-Schritte und O(log n) Rekursionsschritte.
Vielleicht habe ich in Bezug auf die Laufzeit irgendetwas mißverstanden.
chris*
Contributions on this page: 2
View profileOops, da hab ich nicht nachgedacht. Stimmt, es sind immer O(n) Divide-Schritte, aber der Aufwand der Conquer-Schritte ist höher, weil die Rekursionstiefe größer ist.