Asymptotisches Wachstumsverhalten als Vergleichskriterium
Asymptotisches Wachstumsverhalten
Algorithmen sind in der Regel so konzipiert, dass sie eine Lösung für beliebige Problemgrößen liefern. Beim Vergleich zugehöriger Kostenfunktionen tritt die Schwierigkeit auf, dass globale Aussagen oft nicht möglich sind. Es kann vorkommen, dass in einem Bereich die eine Kostenfunktion günstiger ist, in einem anderen Bereich die andere Kostenfunktion. Die Abbildung zeigt eine solche Situation für die Kostenfunktionen T1(n) = 0.01*n2 (rot) und T2(n) = 100*n*log10(n) (blau).
Oft ist der Problembereich, für den Algorithmen benötigt werden, nicht klar vorgegeben. Man benötigt dann ein Vergleichsverfahren für Kostenfunktionen, das auch mit Situationen wie in der Abbildung klarkommt.
Eine Grundidee des in der Informatik gängigen Vergleichsverfahrens besteht darin, dass kleine Problemgrößen meist von geringerem Interesse sind als große Problemgrößen. Bei kleinen Problemgrößen unterscheiden sich Laufzeiten von Algorithmen z.B. nur im Millisekundenbereich, während die Unterschiede bei großen Problemgrößen im Sekunden-, Minuten-, Stunden-, Tage- oder gar Jahrebereich liegen können. Verbesserungen von Algorithmen zeigen sich in der Regel insbesondere bei großen Problemgrößen.
Mathematisch präzisiert man diese Idee, indem man das Wachstumsverhalten von Kostenfunktionen vergleicht. Dabei idealisiert man, indem man das Grenzwertverhalten für gegen unendlich strebende Problemgrößen betrachtet.
Aufgabe 1
(a) Gegeben ist die Kostenfunktion T1(n) = n*(n-1)/2 = n2/2 - n/2. Untersuche, wie sich T1(n) verhält, wenn man n verdoppelt. Berechne hierzu die konkreten Werte T1(20)/T1(10), T1(200)/T1(100), T1(2000)/T1(1000) usw.. Was fällt auf?
(b) Untersuche entsprechend die Kostenfunktion T2(n) = n*log2(n) und begründe, dass die Kostenfunktion T1(n) schneller wächst als die Kostenfunktion T2(n).
(c) Untersuche auch den Quotienten T2(n)/T1(n). Welches Verhalten zeigt dieser Quotient, wenn n gegen unendlich strebt? Welchen Schluss kann man hieraus über das Wachstumsverhalten der beiden Kostenfunktionen ziehen?
Vergleich von Kostenfunktionen über das asymptotische Wachstumsverhalten
Zum Vergleich von Kostenfunktionen werden die folgenden Begriffe eingeführt.
Eine (Kosten-) Funktion f wächst schneller als eine (Kosten-) Funktion g, wenn der Quotient f(n)/g(n) mit wachsendem n gegen unendlich strebt.
Eine (Kosten-) Funktion f wächst langsamer als eine (Kosten-) Funktion g, wenn der Quotient f(n)/g(n) mit wachsendem n gegen 0 strebt.
Eine (Kosten-) Funktion f wächst genauso schnell wie eine (Kosten-) Funktion g, wenn der Quotient f(n)/g(n) mit wachsendem n gegen eine Konstante c mit c>0 strebt.
Beispiel: f(n) = n2/2-n/2 wächst genauso schnell wie g(n) = n2, da der Quotient f(n)/g(n) mit wachsendem n gegen die Konstante 1/2 strebt.
Beispiel: f(n) = n/2 wächst langsamer als g(n) = n2, da der Quotient f(n)/g(n) mit wachsendem n gegen 0 strebt.
Beispiel: Im Fall der Kostenfunktionen T1(n) = 0.01*n2 und T2(n) = 100*n*log10(n) kann man zeigen, dass der Quotient T2(n) / T1(n) für n gegen unendlich gegen 0 konvergiert. Hieraus schließt man, dass die Kostenfunktion T1(n) schneller wächst als die Kostenfunktion T2(n).
Aufgabe 2
Benutze die eingeführten Begriffe, um die Sortieralgorithmen Selectionsort und Quicksort hinsichtlich des Berechnungsaufwands zu vergleichen. Welche Überlegungen müssen zum Vergleich durchgeführt werden?