i

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

Aufgabe 2

Betrachte auch die beiden (fiktiven) Kostenfunktionen T1(n) = 0.01*n2 und T2(n) = 100*n*log10(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 T3(n) = 2*n2, T4(n) = 10*n2 und T5(n) = n3 anhand einer Wertetabelle. Könnte man erreichen, dass die dazugehörigen Algorithmen gleich schnell ablaufen, indem man sie auf unterschiedlicher Hardware laufen lässt?

Suche

v
2.4.1.4.1
inf-schule.de/algorithmen/komplexitaet/sortieren/asymptotischesverhalten/vergleich
inf-schule.de/2.4.1.4.1
inf-schule.de/@/page/WPCAX5ZrHNja0aFy

Rückmeldung geben