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.