q1:java-sortierverfahrenquicksort

Unterschiede

Hier werden die Unterschiede zwischen zwei Versionen angezeigt.

Link zu dieser Vergleichsansicht

Beide Seiten der vorigen Revision Vorhergehende Überarbeitung
q1:java-sortierverfahrenquicksort [2017/07/11 09:07] – [Aufgabe 2] admin03q1:java-sortierverfahrenquicksort [2017/07/11 09:07] (aktuell) – [Quicksort] admin03
Zeile 45: Zeile 45:
  
 Der **ungünstigste Fall** entsteht, wenn jeweils nur ein 1-Teilfeld abgespaltet wird. Man erhält dann $k=n$ Zerlegungsstufen und damit $$n\cdot \frac{5}{4} \cdot n = \frac{5}{4} \cdot n^2 \sim n^2$$ Operationen, das Laufzeitverhalten des Sortierverfahrens ist dann quadratisch. Dieser ungünstigste Fall wird erreicht, wenn das Vergleichselement jeweils das größte oder kleinste Element im Teilfeld ist. Der **ungünstigste Fall** entsteht, wenn jeweils nur ein 1-Teilfeld abgespaltet wird. Man erhält dann $k=n$ Zerlegungsstufen und damit $$n\cdot \frac{5}{4} \cdot n = \frac{5}{4} \cdot n^2 \sim n^2$$ Operationen, das Laufzeitverhalten des Sortierverfahrens ist dann quadratisch. Dieser ungünstigste Fall wird erreicht, wenn das Vergleichselement jeweils das größte oder kleinste Element im Teilfeld ist.
 +
 +
 +====== Aufgaben ======
  
  
  • /var/www/infowiki/data/attic/q1/java-sortierverfahrenquicksort.1499764036.txt.gz
  • Zuletzt geändert: 2017/07/11 09:07
  • von admin03