Angenommen Quicksort wählt das Pivotelement in jedem Schritt so,

Question

dass das Verhältnis der Längen der beiden Teilfolgen \(0 < α < \frac { 1 }{ 2 }\) beträgt. Zeigen Sie, dass in diesem Fall die Laufzeit von Quicksort aus \(O(n·log(n))\) ist.

Hinweis: Vernachlässigen Sie die Rundungen auf ganze Zahlen und zeigen Sie in einem Zwischenschritt, dass die Rekursionstiefe nährungsweise\( \frac { -log(n) }{ log(1−α ) }\) ist

Könnte jemand Helfen?

Answer 1

Die Rekursionsformel fuer die Laufzeit waere $$T(n)=T(\alpha n)+T\bigl((1-\alpha) n\bigr).$$ Da \(\alpha<1/2\) ist der zweite Teil der teurere: $$T(n)<2T\bigl((1-\alpha) n\bigr).$$ Ein bisschen Rumspielen ergibt $$T(n)<2T\bigl((1-\alpha) n\bigr)<2^2T\bigl((1-\alpha)^2 n\bigr)<\cdots<2^\ell T\bigl((1-\alpha)^\ell n\bigr).$$ Zur Basis \(T(1)\) der Rekursionsformel kommt man, wenn $$(1-\alpha)^\ell n=1$$ wird. Das macht dann wie vorgeschlagen $$\ell=-\frac{\log n}{\log(1-\alpha)}.$$

PS: Ich sehe gerade, dass da noch ein Term fuer die Laufzeit der Partitionierung fehlt. Aber den kannst Du selber nachtragen. Die Idee stimmt.

Comments

Mit Partitionierungszeit: $$T(n)=T(\alpha n)+T\bigl((1-\alpha)n\bigr)+cn.$$ Die Abschaetzung ist dann $$T(n)<2T\bigl((1-\alpha)n\bigr)+cn<2^2T\bigl((1-\alpha)^2n\bigr)+2cn<2^3T\bigl((1-\alpha)^3n\bigr)+3cn<\cdots<2^\ell T\bigl((1-\alpha)^\ell n\bigr)+\ell cn,$$ wobei nur die Zeit fuer die Rekursion abgeschaetzt wird, der Partitionierungsaufwand ist exakt mitgenommen.

Ansonsten wie oben.