Landau-Symbole
Notation zur Beschreibung des asymptotischen Verhaltens von Funktionen und Folgen / aus Wikipedia, der freien encyclopedia
Liebe Wikiwand-AI, fassen wir uns kurz, indem wir einfach diese Schlüsselfragen beantworten:
Können Sie die wichtigsten Fakten und Statistiken dazu auflisten Landau-Symbole?
Fass diesen Artikel für einen 10-Jährigen zusammen
Landau-Symbole (auch O-Notation, englisch big O notation) 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 oder der Speichereinheiten in Abhängigkeit von der Größe des gegebenen Problems an.
Die Komplexitätstheorie verwendet sie, um Probleme danach zu klassifizieren, wie „schwierig“ oder aufwändig sie zu lösen sind. Zu „leichten“ Problemen existiert ein Algorithmus, dessen Laufzeit sich durch ein Polynom beschränken lässt; als „schwer“ gelten Probleme, für die man keinen Algorithmus gefunden hat, der weniger schnell als exponentiell wächst. Man nennt sie (nicht) polynomiell lösbar.
Notation | Anschauliche Bedeutung
(immer ohne Berücksichtigung von Konstanten) |
---|---|
oder |
wächst langsamer als |
oder |
wächst höchstens genauso schnell wie |
wächst genauso schnell wie | |
wächst nicht immer langsamer als (Zahlentheorie) | |
wächst mindestens genauso schnell wie (Komplexitätstheorie) | |
wächst schneller als |