0 Daumen
761 Aufrufe

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?

Avatar von

1 Antwort

0 Daumen

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.

Avatar von

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.

Ein anderes Problem?

Stell deine Frage

Ähnliche Fragen

Willkommen bei der Stacklounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community