• Artikel
• Bearbeiten
• Historie
• Druckansicht

O-Notation

Die O-Notation wird in der Informatik verwendet um das asymptotische Verhalten von Funktionen und Folgen zu beschreiben. In der Komplexitätstheorie wird sie verwendet, um verschiedene Probleme und Algorithmen danach zu vergleichen, wie "schwierig" oder aufwendig sie zu berechnen sind.

Groß O und klein o sind die am häufigsten verwendeten Landau-Symbole; darüber hinaus gibt es noch Ω, ω und Θ.

asymptotische obere Schranke

asymptotische untere Schranke

Sprechweise

	T ist in O von g
	g wächst mindestens so schnell wie T
	T und g sind von der gleichen Wachstumsordnung

Es gilt

Weblinks

• http://de.wikipedia.org/wiki/O-Notation