Thomas Kramer

IT-COW | All posts tagged '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.

 

Monats-Liste