Landau-Symbole

---

Zusammenfassung

Die Landau-Symbole beschreiben das asymptotische Verhalten (also bei von Funktionen und Folgen.

Sie werden insbesondere für die Analyse von Algorithmen verwendet und geben ein Maß für die Anzahl der benötigten Schritte oder Speichereinheiten.

Sie können auch genutzt werden, um zu klassifizieren, wie “schwierig” oder “aufwändig” Probleme sind.

Definition

Klein-o

wächst echt langsamer als

Groß-O

wächst nicht wesentlich schneller als . Man sagt auch, ist eine (asymptotische) obere Schranke.

Sei ein Startpunkt und eine konstante:

(Was bedeutet das mit lim sup?)

Groß-Omega

wächst nicht wesentlich langsamer als Man sagt auch, ist eine (asymptotische) untere Schranke für .

Das heißt:

(Was bedeutet das mit lim inf?)

Klein-omega

wächst schneller als Man sagt auch, ist asymptotisch dominant für ( wächst also viel schneller)

Das heißt:

(Was bedeutet das mit lim?)

Groß-Theta

wächst genauso schnell wie . Es gilt

und verhalten sich (bis auf einen konstanten Faktor) asymptotisch gleich.

Beziehungsweise gilt

Tilde

verhalten sich gleich.

HINT

Das heißt, für große geht der Fehler gegen null. Es gilt mit , geht also gegen 1.

Wichtige Eigenschaften der Landau-Symbole

Summe ist gleich der max. Komplexität

Seien Funktionen mit

So gilt

Exponenten schlagen

Solange

Beachte: beide haben als Basis.

Hoch den Input schlägt alle Konstanten

Solange

Der ln wächst echt langsam

Solange

Wichtige Komplexitätsklassen

Klasse	Name
	konstant
	logarithmisch
	linear
	linearithmisch
	quadratisch
	kubisch
	exponentiell
	faktoriell

---

Appendix

• Tags:
  • Math
  • Komplexitätstheorie
• Reference:
  • } AlgoMathe KE1 - Abschätzungen
  • AlMa
• Related:

---