Version vom 5. Juni 2014, 08:25 Uhr

Landau-Klassen werden in der Informatik verwendet, um das Laufzeitverhalten von Algorithmen (z.B. Sortieralgorithmen) zu beschreiben.

Die Landau-Klassen werden durch ein O gekennzeichnet, z.B. O(n²)

Idee

Die Grundidee der Landau-Klassen besteht darin, die Laufzeit von Algorithmen abschätzen zu können, und zwar

unabhängig von der Rechenleistung des Computers, auf dem sie laufen
unabhängig von der Dauer einer einzelnen Rechenoperation, d.h. jede Operation gilt als gleich "teuer".
unabhängig von einem einmaligen "Startaufwand" (bzw. "Schlussaufwand") zu Beginn (bzw. am Ende) eines Algorithmus

Das "Berechnen" der Laufzeit von Algorithmen wird dadurch radikal vereinfacht, z.B.:

f(n) = n² + 20.000 ϵ O(n²), denn der Startaufwand von 20.000 wird ignoriert!

g(n) = 300 n² ϵ O(n²), denn man könnte einen 300mal so schnellen Computer nehmen und wäre wieder bei n2!

h(n) = n² + 80n ϵ O(n²), denn für große n ist 80n kleiner als n² !

Notation	Bedeutung	Anschauliche Erklärung	Beispiele für Laufzeiten
f ∈ O(1)	f ist beschränkt	f überschreitet einen konstanten Wert nicht (unabhängig vom Wert des Arguments).	Nachschlagen des n-ten Elementes in einem Feld.
f ∈ O(log n)	f wächst logarithmisch	f wächst ungefähr um einen konstanten Betrag, wenn sich das Argument verdoppelt. Die Basis des Logarithmus ist dabei egal.	Binäre Suche im sortierten Feld mit n Einträgen
f ∈ O(n)	linear	f wächst ungefähr auf das Doppelte, wenn sich das Argument verdoppelt.	Suche im unsortierten Feld mit n Einträgen (Bsp. Lineare Suche)
f ∈ O(n ∗ log n)	f hat super-lineares Wachstum		Fortgeschrittenere Algorithmen zum Sortieren von n Zahlen Mergesort, Quicksort (im Average Case)
f ∈ O(n²)	quadratisch	f wächst ungefähr auf das Vierfache, wenn sich das Argument verdoppelt	Einfache Algorithmen zum Sortieren von n Zahlen Selectionsort
f ∈ O(n!)	f wächst mit der Fakultät	f wächst ungefähr auf das (n+1)-fache, wenn sich das Argument um eins erhöht.	Problem des Handlungsreisenden

@@ Zeile 1: / Zeile 1: @@
+[[Kategorie:Informatik]]
+Landau-Klassen werden in der Informatik verwendet, um das Laufzeitverhalten von Algorithmen (z.B. Sortieralgorithmen) zu beschreiben.
+Die Landau-Klassen werden durch ein '''O''' gekennzeichnet, z.B. '''O'''(n<sup>2</sup>)
+=Idee=
+Die Grundidee der Landau-Klassen besteht darin, die Laufzeit von Algorithmen abschätzen zu können, und zwar
+* unabhängig von der Rechenleistung des Computers, auf dem sie laufen
+* unabhängig von der Dauer einer einzelnen Rechenoperation, d.h. jede Operation gilt als gleich "teuer".
+* unabhängig von einem einmaligen "Startaufwand" (bzw. "Schlussaufwand") zu Beginn (bzw. am Ende) eines Algorithmus
+=Bestimmung von Landau-Klassen für Funktionen=
+Das "Berechnen" der Laufzeit von Algorithmen wird dadurch radikal vereinfacht, z.B.:
+f(n) = n<sup>2</sup> + 20.000 ϵ '''O(n<sup>2</sup>)''', denn der Startaufwand von 20.000 wird ignoriert!
+g(n) = 300 n<sup>2</sup> ϵ '''O(n<sup>2</sup>)''', denn man könnte einen 300mal so schnellen Computer nehmen und wäre wieder bei n2!
+h(n) = n<sup>2</sup> + 80n ϵ '''O(n<sup>2</sup>)''', denn für große n ist 80n kleiner als n<sup>2</sup> !
+=Wichtige Landau-Klassen=
 {| class="wikitable"
 |-