Aufwandsabschätzungen

Warum Aufwandsabschätzungen?

Laufzeitmessungen liefern wichtige Informationen über die Einsetzbarkeit von Programmen. Programme, bei denen man sehr lange auf Ergebnisse warten muss, sind - je nach Anwendungsgebiet - oft nicht praxistauglich. So ist ein Programm zur Bestimmung der Primfaktoren einer vorgegebenen Zahl sicher nicht bei großen Zahlen einsetzbar, wenn man Minuten, Stunden oder gar Tage auf ein Ergebnis warten muss.

Experimentell bestimmte Laufzeiten haben auch den Nachteil, dass sie vom benutzen Rechner und den Bedingungen auf dem Rechner (Prozesse, die dort laufen) abhängen. Laufzeiten sind also nur bedingt aussagekräftig. Bei manchen Problemstellungen können sie zudem so groß werden, dass man sie nicht ermitteln kann.

Neben experimentellen Methoden benutzt man in der Informatik daher auch mathematische Methoden zur Beschreibungen des Laufzeitverhaltens. Man versucht dabei, das Laufzeitverhalten abzuschätzen und abstrahierend zu beschreiben.

Die Problemgröße erfassen

Die Problemgröße ist eine präzise Beschreibung des Umfangs der zu verarbeitenden Daten, von dem das Laufzeitverhalten (bzw. das Speicherverhalten) maßgeblich beeinflusst wird.

Das Problem hier besteht darin, zu einer vorgegebene natürlichen Zahl n ihre Primfaktordarstellung zu bestimmen. Ein kleines Problem wäre beispielsweise die Bestimmung der Primfaktordarstellung von n = 24. Ein vergleichsweise großes Problem bestünde darin, die Primfaktordarstellung von n = 775517959261225265313877628572204089387832653836742449 zu bestimmen.

Die Problemgröße könnte hier durch die Zahl n selbst beschrieben werden. Eine andere Möglichkeit bestünde darin, die Problemgröße durch die Anzahl der Dezimalstellen von n zu erfassen. Die zweite Möglichkeit erweist sich als günstiger, wenn man das Wachstumsverhalten des Berechnungsaufwands bei großen Zahlen abschätzen möchte. Wir werden daher die Problemgröße im Folgenden über die Anzahl der Dezimalstellen der zu verarbeitenden Zahl beschreiben. Während das kleine Problem mit dieser Festlegung die Problemgröße 2 hat, ergibt sich beim großen Problem die Problemgröße 54.

Den Berechnungsaufwand beschreiben

Bei der Ausführung eines Programms spielt es eine Rolle, wie viele Operationen (Zuweisungen, Vergleiche etc.) ausgeführt werden müssen. In der Regel ist es schwierig, den Beitrag der verschiedenen Operationen zur gesamten Laufzeit exakt zu beschreiben. Man beschränkt sich oft darauf, dominante Operationen auszuwählen und den Berechnungsaufwand somit nur grob zuzuschätzen.

Im vorliegenden Fall ist die dominante Operation bei der Primfaktorzerlegung die Probedivision. Die Laufzeit hängt also wesentlich davon ab, wie viele solcher Probedivisionen ausgeführt werden.

Als Kostenmaß zur Abschätzung des Berechnungsaufwands (bei dem hier benutzten Algorithmus zu Primfaktorzerlegung) wählen wir also die Anzahl der auszuführenden Probedivisionen.

Die Kosten abschätzen

Eine erste Schwierigkeit besteht darin, dass bei gegebener Problemgröße die Kosten ganz unterschiedlich ausfallen können. Bei gleicher Problemgröße sind bei manchen Zahlen nur ganz wenige Probedivisionen erforderlich, bei anderen hingegen sehr viele.

Aufgabe 1

Überlege dir Fälle, in denen besonders wenige / besonders viele Probedivisionen erforderlich sind.

Bei einer Kostenanaylse unterscheidet man oft die folgenden Fälle:

• best case (bester Fall): der Fall, in dem bei der Ausführung des Algorithmus die wenigsten Kosten anfallen
• worst case (schlechtester Fall): der Fall, in dem bei der Ausführung des Algorithmus die meisten Kosten anfallen
• average case (durchschnittlicher Fall): eine Mittelung der Kosten über alle Fälle

Im best case ist die vorgegebene Zahl n eine 2er-Potenz. Die jeweils erste auszuführende Probedivision liefert dann immer den nächsten Primfaktor. In diesem Fall werden log₂(n) Probedivisionen durchgeführt.

Im worst case ist die vorgegebene Zahl n eine Primzahl. Hier muss man alle Probedivisionen durchführen, um den ersten und einzigen Primfaktor zu finden. Insgesamt sind √(n) - 1 Probedivisionen durchzuführen.

Auf eine Analyse des average case verzichten wir, da eine solche Analyse viel zu schwierig ist.

Das asymptotische Verhalten der Kosten untersuchen

Die Kostenfunktion K(i) ordnet der Problemgröße i (d.h. der Anzahl der Dezimalstellen der Ausgangszahl) die Gesamtkosten (d.h. die Anzahl der erforderlichen Probedivisionen) zu.

Betrachten wir erst den ungünstigsten Fall (worst case): Wenn man eine Primzahl mit i Dezimalstellen vorgibt, so liegt sie zwischen 10^i-1 und 10ⁱ. Es werden dann mindestens √(10^i-1) = (√10)^i-1 Probedivisionen ausgeführt.

Die Kosten bei einer Problemgröße i betragen demnach im ungünstigsten Fall mindestens (√10)^i-1. Die Kostenfunktion ist (abgeschätzt) also eine Exponentialfunktion mit der Basis √10. Wenn man die Problemgröße um 1 erhöht, dann wachsen die Kosten mit dem Faktor √10. Wenn man die Problemgröße um 2 erhöht, dann wachsen die Kosten mit dem Faktor √10*√10, also mit dem Faktor 10. Beachte, dass wir hier ein Ergebnis erhalten, das den Laufzeitmessungen entspricht.

Betrachten wir auch den günstigsten Fall (best case): Wenn man eine 2er-Potenz mit i Dezimalstellen vorgibt, so beträgt sie höchstens 2^4*i, da 10 < 2⁴. Es werden dann höchstens 4*i Probedivisionen ausgeführt.

Die Kosten bei einer Problemgröße i betragen demnach im günstigsten Fall höchstens 4*i. Die Kostenfunktion ist (abgeschätzt) also eine lineare Funktion. Wenn man die Problemgröße um 1 erhöht, dann wachsen die Kosten um einen festen Betrag.

Anwendbarkeit des Algorithmus

Algorithmen, deren Zeitkomplexität durch eine Kostenfunktion beschrieben wird, die exponentiell oder noch schneller wächst, gelten als praktisch nicht anwendbar.

Die folgenden Überlegungen verdeutlichen dies anhand des naiven Faktorisierungsalgorithmus. Angenommen, der Rechenaufwand beträgt bei einer zu faktorisierenden Zahl mit 10 Stellen 1 Zeiteinheit, dann beträgt der Rechenaufwand bei einer Zahl mit 100 Stellen 10⁴⁵ Zeiteinheiten. Beachte, dass man heute tatsächlich mit Zahlen dieser Größenordnung arbeitet. Wenn sich die Rechnergeschwindigkeit um den Faktor 1000 verbessert, dann beträgt der Rechenaufwand immer noch 10⁴² Zeiteinheiten. Auch wenn die Zeiteinheit gering ist, es ergeben sich nichtsdestotrotz riesige Rechenzeiten, die in der Praxis nicht abgewartet werden können.