O-Notation
Die O-Notation beschreibt die Qualität eines Algorithmus (nicht jedoch die Qualität der Implementierung!). Meistens wird die Laufzeit betrachtet, jedoch kann die O-Notation beispielsweise auch für den Speicherbedarf verwendet werden.
Die O-Notation besagt (sehr grob ausgedrückt): Die maximale Laufzeit für n Elemente übersteigt nicht die durch Faktor * O( f(n) ) angegebene Funktion.
Es handelt sich also um eine stark vereinfachte Berechnung des Laufzeitverhalten. Es fließen dabei nicht mit ein:
- Initialisierungen und Vorberechnungen (die O-Notation ist für hohe Wertebereiche ausgelegt)
- kleine Nebenberechnungen (da sie bei hohen Wertebereichen keine Rolle mehr spielen)
- Den Faktor (welcher stark von der Implementierung und der Hardware abhängen kann)
Dadurch gilt also:
- O( n*n + 10*n + 100 ) = O( n*n ): Initialisierungen und kleine Nebenberechnungen weg lassen
- O( 3*n ) = O( n ): Faktoren weg lassen
- O( ld( n ) ) = O( log( n ) ): Faktoren weg lassen ( ld( n ) = log( n ) / log( 2 ) )
- O( n ) darf als O( n*n ) geschrieben werden: n übersteigt ab einem gewissen Wert X niemals n*n
- O( n*n ) darf nicht als O( n ) geschrieben werden: n*n übersteigt bei hohen Wertebereichen n => nicht gültig
Typische Algorithmen und ihre Laufzeiten:
- O( 1 ): Zugriff auf ein Element in einem Array
- O( log(n) ): Element suchen in einer Baumstruktur
- O( n ): Element suchen in einer Liste oder einem unsortierten Array
- O( n*log(n) ): Gute Sortieralgorithmen wie zB Quicksort
- O( n*n ): Schlechte Sortieralgorithmen wie zB Bubblesort
Wozu sollte die O-Notation verwendet werden:
- Für einen groben Vergleich von Algorithmen
- Für eine grobe Einteilung der Zeitkomplexität von Algorithmen
- Um besser einschätzen zu können für welche Wertebereiche ein Algorithmus geeignet ist
- Um besser einschätzen zu können wie stark n steigen darf mit der Hardware in einem Jahr (welche etwa doppelt so schnell ist)
Wo sollte die O-Notation mit Vorsicht genossen werden:
- Genaue Bewertung eines Algorithmus (In der praktischen Anwendung laufen viele Algorithmen deutlich schneller als in der pessimistischen Theorie)
Formale Definition:
Seien f(x) und g(x) 2 Funktionen, dann gilt:
f(x) = O( g(x) ) für x -> unendlich
wenn folgende Bediengung zutrifft:
Es gibt 2 Zahlen a und b so dass: f(x) <= b * g(x) für alle x > a
