Thomas Kramer

IT-COW | Die Landau-Symbole

Die Landau-Symbole

By Administrator at Januar 28, 2011 12:39
Filed Under: Studium

In der Fachhochschule war im Grundlagen-Fach zuletzt die sogenannte O-Notation (oft auch Landau-Notation genannt) einer der Schwerpunkte, einer Notation zur Qualitätsbewertung von Algorithmen.

 

Es handelt sich hierbei um eine stark vereinfachte Berechnung des Laufzeit- oder Speicherplatzverhaltens. In den meisten Fällen wird damit nur das Laufzeitverhalten betrachtet.

 

Die O-Notation bewertet die obere Schranke, die Omega-Notation die untere Schranke - daneben gibt es noch die Theta-Notation für den Fall das O- und Omega übereinstimmen. Am wichtigsten ist die O-Notation, um zu bewerten welcher Algorithmus welche Laufzeit maximal erreichen kann.

 

Kompaktere Erklärungen/Zusammenfassungen zu dem Thema sind hier zu finden:

 

 

Gemäß Link zitiere ich einmal die bestimmenden Faktoren bei den verschiedenen Notationen:

 

    Addition f(n) = n + 3 ⇒ f(n) = Θ(n) Konstante Summanden werden vernachlässigt
f(n) = n2 + 3n ⇒ f(n) = Θ(n2) Es zählt der Summand mit dem stärkeren Wachstum
    Multipikation f(n) = 3n ⇒ f(n) = Θ(n) Konstante Faktoren werden vernachlässigt
f(n) = n2 * 3n ⇒ f(n) = Θ(n3) Es zählt die Summe der Exponenten

 

Weiterführende Abhandlungen sind u. a. hier zu finden:

 

 

Genügend Material um sich umfassend damit zu beschäftigen. Das Copyright liegt natürlich bei diesen Seiten, ich mache mir nur Lesezeichen um die Lehrmaterialien schneller wiederfinden zu können.

 

Pingbacks and trackbacks (1)+

Kommentar schreiben




  Country flag
biuquote
  • Kommentar
  • Live Vorschau
Loading


Tag-Wolke

Monats-Liste