Landau-Symbole (O-große Notation)

Landau-Symbole (O-große Notation) wird in der Mathematik und Informatik verwendet, um die asymptotische Komplexität von Algorithmen zu bezeichnen.

Es zeigt, wie sich die Funktion bei großen Werten von Eingabedaten verhält. Grundlegende Bezeichnungen:

O(f(n)) ist die obere Grenze des Funktionswachstums.

Ω(f(n)) ist die untere Grenze.

Θ(f(n)) - präzise Asymptotik.

o(f(n)) ist die strikte obere Grenze.

ω(f(n)) ist die strikte untere Grenze.

Anwendung:

Wird in der Analyse von Algorithmen zur Abschätzung der Arbeitszeit und des Speicherverbrauchs verwendet.

Beispiele:

Blasensortierung - O(n 2).

Schnelle Sortierung - O(n log n).

Binäre Suche - O(log n).

Angewandte in theoretischer Informatik, Datenanalyse, maschinellem Lernen.