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 !