Landau-Klassen: Unterschied zwischen den Versionen
| Zeile 58: | Zeile 58: | ||
|<b>f</b> wächst ungefähr auf das Vierfache, wenn sich das Argument verdoppelt | |<b>f</b> wächst ungefähr auf das Vierfache, wenn sich das Argument verdoppelt | ||
|Einfache Algorithmen zum Sortieren von <b>n</b> Zahlen | |Einfache Algorithmen zum Sortieren von <b>n</b> Zahlen | ||
Selectionsort | Selectionsort, Insertionsort | ||
|- | |- | ||
|<b>f ∈ O(n!)</b> | |<b>f ∈ O(n!)</b> | ||
Aktuelle Version vom 28. November 2016, 15:30 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, Insertionsort |
| 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 |