O-Kalkül


Mithilfe des O-Kakül (oder auch den Landau-Symbolen) kann das asymptotische Verhalten von Funktionen beschrieben werden. Im Kern wird damit versucht, Wachstumsfunktionen anhand ihrer Werteentwicklung in Äquivalenzklassen einzuteilen. Dabei gibt es unterschiedliche Notationszeichen, die sogenannten Landau-Symbole.



Dabei sind folgende Notationen gebräuchlich:

- f wächst nicht wesentlich schneller als g
- f wächst langsamer als g
- f wächst nicht wesentlich langsamer als g
- f wächst schneller als g
- f wächst genauso schnell wie g


Nachfolgend findet man weitere Erläuterungen zu den Notationen.

O-Notation Erklärung

Auf die O-Notation wird man häufig im Zusammenhang von Beschreibungen der Komplexität von Algorithmen stoßen.
So fällt beispielsweise eine Funktion f: Ν → R+ in die Komplexitätsklasse
O(g(n)),
falls es eine Konstante c ∈ von R+ und ein n0 ∈ von N existieren, sodass
f(n) ≤ c*g(n)
für alle n ≥ n0 gilt.

O-Notation Beispiele

Um also zu beweisen, dass eine bestimmte Funktion ∈ O(g(n)) ist, muss man eine entsprechende Konstante finden, für die die obere Definition gilt.

1. Beispiel
Ist f(n)=n3+ 20n + 1 ∈ O(n3)?
Beweis: Ja, falls f(n) ≤ c*n3
es muss also gelten: n3+ 20n + 1 ≤ c*n3, man teilt nun durch n3 und erhält:
⇒ 1+ 20/n2+1/n3 ≤ c
Damit ist bewiesen n3+ 20n + 1 ≤ O(n3) für n ≥ n0=1 und c ≥ 22 (=1+20+1).
Beachte: Natürlich können auch andere Werte für n0 gewählt werden. In diesem Falle ändert sich dann natürlich auch die Konstante, in diesem Beispiel wird sie kleiner. Nimmt man beispielsweise für n0=5, dann ist c ≥ 1,808.




Zitat:



Edsger Wybe Dijkstra:

"Als es noch keine Computer gab, gab es auch das Programmieren als Problem nicht. Als es dann ein paar leistungsschwache Computer gab, wurde das Programmieren zu einem kleinen Problem und nun, wo wir leistungsstarke Computer haben, ist auch das Programmieren zu einem riesigen Problem angewachsen. In diesem Sinne hat die elektronische Industrie kein einziges Problem gelöst, sondern nur neue geschaffen." - The Humble Programmer, ACM Turing Lecture 1972