Rekursionstiefe QuickSort

Neue Frage »

gast20070528 Auf diesen Beitrag antworten »
Rekursionstiefe QuickSort
Hallo,

dass der Quicksort-Algorithmus Rekursionstiefe log n hat, falls das Pivot-Element immer der Median des Teilintervals ist, weiß ich und kann das auch herleiten. Das Problem ist, wenn der Algorithmus in einem anderen Verhältnis teilt. Sei


Dann ist für ein gewisses dann . Dann ist doch aber

Wenn ich das umforme, komme ich auf

Ich weiß auch, dass ich auf kommen muss, sehe den Umformungsschritt aber nicht. Kann mir da jemand helfen?


Danke

gast
gast20070601 Auf diesen Beitrag antworten »

Hallo,

ich werde das ungute Gefühl nicht los, dass mir im Posting ein dämlicher Fehler unterlaufen ist, der alle hier im Forum still vor sich hinkichern lässt...
Beim nochmaligen Durchlesen ist mir aber nichts aufgefallen verwirrt . Oder hat da wirklich niemand Ahnung?


gast
AD Auf diesen Beitrag antworten »

Zitat:
Original von gast20070601
ich werde das ungute Gefühl nicht los, dass mir im Posting ein dämlicher Fehler unterlaufen ist, der alle hier im Forum still vor sich hinkichern lässt...

Du musst nicht gleich so schlecht denken...

Aber einiges ist für Unbeteiligte beim Lesen eben schwer zu verstehen. Ich z.B. stolpere zuerst hier:

Zitat:
Original von gast20070528
Dann ist doch aber

Die linke Ungleichung ist klar für positive , aber die rechte gilt doch nicht für beliebige , sondern nur für bestimmte - wo kommen die her? Das musst du schon noch erklären!


EDIT: Andere Frage: Muss es denn ausgerechnet dieses mit sein? Man findet mühelos ein anderes mit , nämlich

,

da muss man sich nur deine Überlegungen anschauen.
tigerbine Auf diesen Beitrag antworten »

Wegen erhöhter Spamanfälligkeit geschlossen! Wer noch etwas zum thema sagen möchte, bitte email an mich. Danke für euer Verständnis. Wink
Neue Frage »
Antworten »



Verwandte Themen

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