Rekursionstiefe QuickSort |
28.05.2007, 18:47 | gast20070528 | Auf diesen Beitrag antworten » | ||||
Rekursionstiefe QuickSort 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 |
||||||
01.06.2007, 15:43 | 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 . Oder hat da wirklich niemand Ahnung? gast |
||||||
01.06.2007, 17:47 | AD | Auf diesen Beitrag antworten » | ||||
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:
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. |
||||||
20.06.2008, 15:36 | 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. |
|
Verwandte Themen
Die Beliebtesten » |
|
Die Größten » |
Die Neuesten » |
|