6.1Komplexitätstheorie

Landausche O-Notation

Wie schnell wächst der Aufwand mit der Eingabegröße? Die O-Notation vergleicht Funktionen, ohne sich um Konstanten zu kümmern.

Leitformel
f∈O(g)⟺f(n)≤c⋅g(n) ab einem n0f \in O(g) \quad \Longleftrightarrow \quad f(n) \le c \cdot g(n) \ \text{ab einem } n_0
f∈O(g)f \in O(g)⟺f(n)≤c⋅g(n) ab einem n0\Longleftrightarrow f(n) \le c \cdot g(n) \ \text{ab einem } n_0
Lernziel

Funktionen mit o, O, Ω und Θ vergleichen, Wachstumsklassen ordnen und die Rechenregeln der O-Notation anwenden.

Einheit wird geladen …