O-Notation - Versionsgeschichte

Flash am 7. August 2006 um 10:37 Uhr

2006-08-07T10:37:49Z

Lyr: Noch eine kleine Anmerkung

2006-06-30T15:54:27Z

Noch eine kleine Anmerkung

217.227.188.19 am 28. Dezember 2004 um 17:59 Uhr

2004-12-28T17:59:37Z

Lyr am 24. November 2004 um 00:04 Uhr

2004-11-24T00:04:30Z

Lyr am 24. November 2004 um 00:03 Uhr

2004-11-24T00:03:27Z

Lyr: Algorithmen und Laufzeiten korrigiert

2004-11-24T00:01:30Z

Algorithmen und Laufzeiten korrigiert

2004-10-28T01:53:31Z

Neue Seite

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:'''<br>
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

← Nächstältere Version		Version vom 30. Juni 2006, 15:54 Uhr
Zeile 38:		Zeile 38:
	Es gibt 2 Zahlen a und b so dass:		Es gibt 2 Zahlen a und b so dass:
	f(x) <= b * g(x) für alle x > a		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.

@@ Zeile 1: / Zeile 1: @@
 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.
+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:

@@ Zeile 16: / Zeile 16: @@
 '''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

@@ Zeile 31: / Zeile 31: @@
 *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:'''<br>
 Seien f(x) und g(x) 2 Funktionen, dann gilt:

@@ Zeile 17: / Zeile 17: @@
 '''Typische Algorithmen und ihre Laufzeiten:'''
 *O( 1 ): Zugriff auf ein Element in einem Array
-*O( log(n) ): Element suchen in einer Baumstruktur
+*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 Quicksort
+*O( n*log(n) ): Gute Sortieralgorithmen wie zB Heap Sort
 *O( n*n ): Schlechte Sortieralgorithmen wie zB Bubblesort