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