Landau-Klassen: Unterschied zwischen den Versionen

Aus SibiWiki
Zur Navigation springen Zur Suche springen
(Die Seite wurde neu angelegt: „{| class="wikitable" |- ! Notation ! Bedeutung ! Anschauliche Erklärung ! Beispiele für Laufzeiten |- |<b>f ∈ O(1)</b> |<b>f</b> ist beschränkt |<b>f</…“)
 
 
(5 dazwischenliegende Versionen desselben Benutzers werden nicht angezeigt)
Zeile 1: Zeile 1:
[[Kategorie:Informatik]]
[[Kategorie:Algorithmen]]
Landau-Klassen werden in der Informatik verwendet, um das [[Laufzeit_von_Algorithmen|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 n<sup>2</sup>!
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"
{| class="wikitable"
|-
|-
Zeile 35: 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