O-Notation: Unterschied zwischen den Versionen

Version vom 28. Dezember 2004, 18:59 Uhr

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 (ausgeglichenen) Baumstruktur
• O( n ): Element suchen in einer Liste oder einem unsortierten Array
• O( n*log(n) ): Gute Sortieralgorithmen wie zB Heap Sort
• 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)

Beispiel: Quicksort hat eine maximale Laufzeit von O( n*n ), jedoch eine durchschnittliche Laufzeit von O( n*log(n) )

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