Landau-Notation

Landau-Symbole werden in der Mathematik und in der Informatik verwendet, um das asymptotische Verhalten von Funktionen und Folgen zu beschreiben. In der Informatik werden sie bei der Analyse von Algorithmen verwendet und geben ein Maß für die Anzahl der Elementarschritte in Abhängigkeit von der Größe der Eingangsvariablen an. Die Komplexitätstheorie verwendet sie, um verschiedene Probleme danach zu vergleichen, wie „schwierig“ oder aufwendig sie zu lösen sind. Man sagt, „schwere Probleme“ wachsen exponentiell mit der Instanz oder schneller und für „leichte Probleme“ existiert ein Algorithmus, dessen Laufzeitzuwächse sich durch das Wachstum eines Polynoms beschränken lassen. Man nennt sie (nicht) polynomiell lösbar.