Landau-Klassen: Unterschied zwischen den Versionen
| Zeile 1: | Zeile 1: | ||
[[Kategorie:Informatik]] | [[Kategorie:Informatik]] | ||
[[Kategorie:Algorithmen]] | |||
Landau-Klassen werden in der Informatik verwendet, um das Laufzeitverhalten von Algorithmen (z.B. Sortieralgorithmen) zu beschreiben. | Landau-Klassen werden in der Informatik verwendet, um das Laufzeitverhalten von Algorithmen (z.B. Sortieralgorithmen) zu beschreiben. | ||
Version vom 15. September 2015, 10:40 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(n2)
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) = n2 + 20.000 ϵ O(n2), denn der Startaufwand von 20.000 wird ignoriert!
g(n) = 300 n2 ϵ O(n2), denn man könnte einen 300mal so schnellen Computer nehmen und wäre wieder bei n2!
h(n) = n2 + 80n ϵ O(n2), denn für große n ist 80n kleiner als n2 !
Wichtige Landau-Klassen
| 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(n2) | 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 |