Logo des digitalen Schulbuchs inf-schule.de. Schriftzug in Zustandsübergangsdiagramm eines endlichen Automaten.

KIDS

Vergleich von Kostenfunktionen

Kosten beim Sortieren

Wir betrachten die Kosten beim Sortieren durch Auswählen (Selectionsort) und beim Sortieren durch Zerlegen (Quicksort). Die Kosten sollen - wie im letzten Abschnitt - durch die Anzahl der Vergleiche festgelegt werden.

Beim Sortieren durch Auswählen erhält man (in allen Fällen) die Kostenfunktion T(n) = n*(n-1)/2.

Durch statistische Betrachtungen kann man zeigen, dass die Kosten beim Sortieren durch Zerlegen im Mittel durch die Kostenfunktion T(n) = n*log2(n) abgeschätzt werden können.

Aufgabe 1

Welche der Kostenfunktionen ist günstiger? Lege hierzu geeignete Wertetabellen an und begründe deine Einschätzung.

Aufgabe 2

Betrachte auch die beiden Kostenfunktionen T1(n) = 0.01*n2 und T2(n) = 100*n*log10(n). Welche ist günstiger? Lege auch hier geeignete Wertetabellen an. Welche Schwierigkeit tritt bei der Klärung dieser Frage auf?

X

Fehler melden

X

Suche