Landau-Klassen: Unterschied zwischen den Versionen

Aus SibiWiki
Zur Navigation springen Zur Suche springen
 
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 &isin; O(n!)</b>
|<b>f &isin; 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