O-Notation
Die O-Notation beschreibt als reduziertes Geschwindigkeitsgesetz eines Algorithmus' die Entwicklung der Laufzeit in Abhängigkeit von der eingegebenen Datenmenge. Sie vernachlässigt dabei Absolutglieder und ggf. lineare Vorfaktoren und betrachtet nur den Teil der Funktion, der für den Grenzwert für "x gegen unendlich" entscheidend ist.
Interessant ist dies in z.B. beim Vergleich des Needleman-Wunsch-Algorithmus mit einem naiven Algorithmus zum Vergleich von Sequenzen: Während die Laufzeit des naiven (nicht dynamisch programmierten) Algorithmus' exponentiell mit der Sequenzlänge wächst und schon ab Sequenzlängen von wenig über 10 Zeichen irrational lange Zeiträume zur Berechnung benötigen würde, steigt die Laufzeit des Needleman-Wunsch-Algorithmus quadratisch mit der Sequenzlänge und ist dadurch auch für Sequenzen von mehreren hundert Zeichen noch problemlos an unseren heutigen Rechnern zu verwenden.
Die Schaubilder zeigen die Abhängigkeit der Zahl der Rechenoperationen, die ein Computer ausführen muss, in Abhängigkeit von der O-Notation eines Algorithmus':
Zunächst die Entwicklung bei einer Sequenzlänge von bis zu 8 Zeichen:
Nun für Sequenzlängen bis zu 18:
Bei einer Sequenzlänge von 50 Zeichen erreicht der naive Algorithmus bereits eine Zahl von
1 259 000 000 000 000 notwendigen Rechenschritten...