O-Notation: Unterschied zwischen den Versionen

Aktuelle Version vom 7. August 2006, 11:37 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

Einschränkungen

Anzumerken sei noch, dass man bei der O-Notation üblicherweise weitere Annahmen trifft. So benötigt man zum Beispiel für das addieren von 2 Zahlen nicht eine Laufzeit von O(1) sondern O(n), wobei n die Anzahl der Bit dieser Zahlen ist. Dies wird jedoch üblicherweise vernachlässigt, da man sich meist mit Zahlen mit fixer Größe (heutzutage 32 oder 64 Bit) zufrieden gibt. Es spielt jedoch durchaus eine Rolle, wenn es beispielsweise um Mathematik-Bibliotheken mit beliebig großen Zahlen geht.

Der umgekehrte Fall kann jedoch eintreffen wenn man einen Algorithmus für parallele Rechner implementiert. In diesem Fall existiert häufig auch eine kleinere obere Schranke für einen Algorithmus.