vorige

Berechnungsaufwand


Fragen des Berechnungsaufwandes tauchen nicht bei Problemen auf, bei denen einzelne Aufgaben zu erledigen sind, sondern nur dann, wenn (fast) dieselben Arbeitsschritte sehr oft wiederholt werden. In der Regel gibt es für die Frage, wie oft im Algorithmus diese Arbeitsschritte wiederholt werden, einen vom Problem abhängenden Parameter N. Bei unseren Problemen, die sich mit Graphen beschreiben lassen, ist das in der Regel die Zahl der Knoten des Graphen. Von ihr hängt bei einer vollständigen Untersuchung ab, wie oft nach einander eine Expansion durchgeführt werden muss, um überhaupt zu einem Blatt des Expansionsbaumes zu gelangen. Folgende wichtigen prinzipiellen Abhängigkeiten vom Parameter N treten allgemein in Algorithmen auf:

Diese

1
konstant
Anweisungen werden nur einfach oder mit kleiner Zahl ausgeführt, egal wie groß N ist.
log N
logarithmisch
Der Aufwand wächst langsamer als die Zahl N.
N
linear
Der Aufwand wächst proportional zur Zahl N. Dies tritt z.B. bei einem Algorithmus auf, bei dem eintreffende Daten einfach bearbeitet und weitergereicht werden.
Beispiel: Ein Algorithmus zur Verschlüsselung, der mit einem Blockchiffre arbeitet.
N * log N Der Aufwand wächst etwas schneller als proportional zu N.
Typisch z.B. bei den "guten" Sortieralgorithmen wie binärem Einfügen.
N 2
quadratisch
Der Aufwand wächst quadratisch mit N.
Typisch z.B. bei den "schlechten" Sortieralgorithmen wie linearem Einfügen.
Dabei tritt eine Schachtelung einer inneren in eine äußere Schleife auf.
In jedem Schritt müssen im Mittel N/2 Positionen bearbeitet werden und das jeweils für N Elemente .
N 3
kubisch
entsprechend
b N
exponentiell
Der Aufwand wächst exponentiell mit N.
Viele kennen das Beispiel mit den Reiskörnern auf dem Schachbrett.
Hier ist das Problem geschachtelt.
b ist der Verzweigungsgrad des Expansionsgraphen.
Die möglichen Züge beim Schachspiel haben solch ein Verhalten.

Ausführliche Untersuchungen zu diesem Thema finden Sie u.a. bei Sedgewick im Kapitel zur Analyse von Algorithmen.

Stellt man diese Zusammenhänge in Zahlen dar, erhält man z.B. die folgende Tabelle:

Abhängigkeit der Zahl der Arbeitsschritte von N
log N N N log N N 2 N 3 2 N
3 10 30 100 1000 ca. 1000
6 100 600 10.000 1.000.000 ca. 10 30
9 1.000 9.000 1.000.000 1.000.000.000 ca. 10 300 *)
13 10.000 130.000 100.000.000 10 12 ca. 10 3.000
16 100.000 1.600.000 10.000.000.000 10 15 ca. 10 30.000
19 1.000.000 19.000.000 1.000.000.000.000 10 18 ca. 10 300.000
O(log(N)) O(N) O(N*log(N)) O(N 2) O(N 3) O(2 N)

*) schon das ist nichts mehr für Taschenrechner !