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*log₂(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 T₁(n) = 0.01*n² und T₂(n) = 100*n*log₁₀(n). Welche ist günstiger? Lege auch hier geeignete Wertetabellen an. Welche Schwierigkeit tritt bei der Klärung dieser Frage auf?