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. Falls du eine Tabellenkalkulation nutzt, dann erstelle auch ein Diagramm.

Aufgabe 2

Betrachte auch die beiden (fiktiven) Kostenfunktionen T₁(n) = 0.01*n² und T₂(n) = 100*n*log₁₀(n). Welche ist günstiger? Lege auch hier geeignete Wertetabellen und eventuell ein Diagramm an. Welche Schwierigkeit tritt bei der Klärung dieser Frage auf? (Tipp: Der Schein trügt zuerst.)

Aufgabe 3

Vergleiche auch die (fiktiven) Kostenfunktionen T₃(n) = 2*n², T₄(n) = 10*n² und T₅(n) = n³ anhand einer Wertetabelle. Könnte man erreichen, dass die dazugehörigen Algorithmen gleich schnell ablaufen, indem man sie auf unterschiedlicher Hardware laufen lässt?