Landau-Symbole

Notation ! Anschauliche Bedeutung
	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

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.

Copyright- und Lizenzinformationen: Diese Seite basiert auf dem Artikel Landau-Symbole aus der freien Enzyklοpädιe Wιkιpedιa und steht unter der Lizenz Creative Commons CC-BY-SA 3.0 Unported (Kurzfassung). Liste der Autoren