Laufzeit von Quicksort < Algor.+Datenstr. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Aufgabe | Zeigen Sie, dass Quicksort bei Eingabe eines absteigend sortierten Arrays der Größe n eine Laufzeit von [mm] O(n^{2}) [/mm] benötigt.
QUICKSORT(l,p,r)
if p < r then
q = PARTITION(l,p,r)
QUICKSORT(l,p,q-1)
QUICKSORT(l,q+1,r)
wobei PARTITION(l,p,r) gruppiert von l[p,...,r] ebtsprechend dem Pivotelement l[r], so dass links von q nur Elemente [mm] \le [/mm] l[r], und rechts von q nur Elemente [mm] \ge [/mm] l[r] |
Hallo Forum,
ich hab ein Problem zu dieser Aufgabe, weil ich überhaupt nicht weiß, wie ich das zeigen soll. In einem Buch hab ich gelesen, dass man das mit der Substitutionsmethode zeigt, aber leider haben wir diese Methode nicht in der Vorlesung behandelt. Wie kann ich das denn sonst beweisen? Ich kenne nur die Mastermethode. Diese hab ich auch auf das problem angewendet, aber bei mir kommt für die Laufzeit T(n) = O(n) heraus und nicht [mm] O(n^{2}).
[/mm]
Ich hab das so gemacht: Es gilt ja T(n) = T(n-1)+ T(0) + O(n) (das Pivotelement ist das kleinste, daher T(n-1) und T(0))
Nach der Anwendung der Mastermethode hab ich dann O(n) = [mm] omega(n^{0 + \epsilon}), [/mm] sei [mm] \epsilon [/mm] = 1.
Dann bekomme ich aber T(n) = O(n).
Ich weiß nicht, wie das sonst gehen soll.
Ich hoffe es kann mir jemand weiter helfen.
Danke vielmals,
wetterfrosch
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 23:50 Di 09.05.2006 | | Autor: | Frank05 |
> QUICKSORT(l,p,r)
> if p < r then
> q = PARTITION(l,p,r)
> QUICKSORT(l,p,q-1)
> QUICKSORT(l,q+1,r)
> ich hab ein Problem zu dieser Aufgabe, weil ich überhaupt
> nicht weiß, wie ich das zeigen soll. In einem Buch hab ich
> gelesen, dass man das mit der Substitutionsmethode zeigt,
> aber leider haben wir diese Methode nicht in der Vorlesung
> behandelt. Wie kann ich das denn sonst beweisen? Ich kenne
> nur die Mastermethode. Diese hab ich auch auf das problem
> angewendet, aber bei mir kommt für die Laufzeit T(n) = O(n)
> heraus und nicht [mm]O(n^{2}).[/mm]
> Ich hab das so gemacht: Es gilt ja T(n) = T(n-1)+ T(0) +
Du brauchst einen Faktor vor dem n für die Mastermethode. Das -1 spielt keine Rolle.
> O(n) (das Pivotelement ist das kleinste, daher T(n-1) und
> T(0))
> Nach der Anwendung der Mastermethode hab ich dann O(n) =
> [mm]omega(n^{0 + \epsilon}),[/mm] sei [mm]\epsilon[/mm] = 1.
Wie kommst du auf die 0 ?
> Dann bekomme ich aber T(n) = O(n).
> Ich weiß nicht, wie das sonst gehen soll.
> Ich hoffe es kann mir jemand weiter helfen.
Ich denke du verkopfst dich da viel zu sehr mit dem Master Theorem. Lass einfach mal die ganzen tollen Sätze weg und überleg dir was da passiert.
Erster Aufruf führt dazu, dass PARTITION aufgerufen wird. Dabei werden n-1 Vergleiche gemacht, um eine Aufteilung in eine n-1 elementige und eine 0-elementige Liste zu erledigen. Die 0-elementige interessiert nicht weiter, und jetzt überleg dir nochmal was passiert, wenn der zweite QUICKSORT Aufruf erfolgt. Wieviele Vergleiche werden benötigt? Wieviele Elemente verbleiben in der Liste (wird ja wieder nur eine).. und dann brauchst du nur noch die Summe über diese Vergleichsanzahlen bilden und bist fertig.
Mit Master Theorem brauchst du da nicht wirklich draufschiessen, weil es im worst-case eben gerade keine interessante Rekursion ist, sondern linear betrachtet werden kann. Einmal eine Schleife, um immer ein Element weniger zu betrachten, einmal eine Schleife für PARTITION und schon hast du intuitiv das [mm]n^2[/mm] begründet.
|
|
|
| |
|
Hallo,
erstmal vielen Dank für deine Antwort. Ich hab mir folgendes überlegt:
Die Anzahl der Vergleiche beim 2.Quicksortaufruf sind n-2 oder? Ich vermute jetzt mal, dass die Anzahl der Vergleiche bei jedem Quicksortaufruf dich um 1 verringert, stimmt das?
Demzufolge ist dann die Gesamtanzahl der Vergleiche (n-1)+(n-2)+......+1 = [mm] \summe_{i=1}^{n-1} [/mm] i = [mm] \bruch{n(n-1)}{2}, [/mm] und das ist in [mm] Teta(n^{2}), [/mm] was zu zeigen war.
Ich hoffe, das stimmt so.
Viele Grüße,
wetterfrosch
|
|
|
| |
|
Hallo,
vielen Dank für deine Antwort :)
LG, wetterfrosch
|
|
|
|
![[daumenhoch]](/images/smileys/daumenhoch.gif "[daumenhoch]"){kind=small}
![[cap]](/images/smileys/cap.gif "[cap]"){kind=small}
