Hasso-Plattner-Institut
  
Hasso-Plattner-Institut
Prof. Dr. Tobias Friedrich
  
 

O-Notation

Autor: Timo Kötzing

Hier lernst du, wie man verschiedene Terme in der O-Notation (Landau-Notation) vergleicht. Dazu musst du dich zuallererst mit Logarithmen und Exponentiationsregeln auskennen. Falls du da unsicher bist, findest du unsere Lernheit dazu hier. Wir lernen das Vergleichen in den folgenden vier Schritten.

  1. Klassifikation: polynomielles, superpolynomielles und subpolynomielles Wachstum;
  2. Ordnen: Die O-Notation;
  3. Weitere Landau-Symbole.

Alle Teile geben dir zuerst ein paar Erklärungen, gefolgt von Übungen. Wir legen fest, dass alle Logarithmen auf dieser Seite zur Basis 2 genommen werden.


Klassifikation

Wir sagen, dass ein Term \(f(n)\) polynomielles Wachstum hat, falls es \(c,d \gt 0\) gibt, so dass $$ \exists n_0: \forall n \geq n_0: n^c \leq f(n) \leq n^d. $$ Dabei darf das \(c\) beliebig klein werden (solange es nicht von \(n\) abhängt). Hat \(\sqrt{n}\) polynomielles Wachstum? Mit unserer Definition ja, da \(\sqrt{n} = n^{1/2}\). Um entscheiden zu können, ob ein Term polynomielles Wachstum hat, müssen wir deshalb seine Defition transformieren, so dass wir den Term schreiben als \(n\) hoch irgendwas; wenn dieses irgendwas gegen \(0\) konvergiert, dann wächst der Term nur langsam (wir nennen dies subpolynomielles Wachstum); wenn es gegen unendlich geht, dann wächst der Term schnell (genannt superpolynomielles Wachstum). Nur wenn er durch Konstanten \(c,d \gt 0\) beschränkt ist, sprechen wir von polynomiellen Wachstum.

Beispiele: $$ \sqrt{n^4} = n^{4/2} = n^2; $$ $$ 2^n = 2^{n \cdot \log(n)/\log(n)} = n^{n / \log(n)}; $$ $$ \log(n) = 2^{\log(\log(n))} = 2^{\log(\log(n)) \cdot \log(n)/\log(n)} = n^{\log(\log(n))/\log(n)}. $$ Wie du sehen kannst, ist der Exponent im ersten Beispiel konstant (polynomielles Wachstum); im zweiten Beispiel geht der Exponent gegen unendlich (superpolynomielles Wachstum); und im dritten Beispiel konvergiert der Exponent gegen 0 (subpolynomielles Wachstum).

Kannst du diese Termtransformationen im Kopf machen? Falls nicht, hol dir jetzt Papier und Stift!


Jetzt bist du dran. Benutze drag and drop, um die folgenden Terme in die passenden Kategorien einzuteilen. Verwende Termtransformation wie oben beschrieben. Du wirst sehen, dass es bei falschen Einteilungen keine Hinweise dazu gibt, welche Elemente falsch platziert sind. Es gibt auch keine Antwort, bevor nicht alle Terme platziert sind. Einfach nur ausprobieren lehrt nicht, wie man Terme in O-Notation vergleicht, man muss die Terme umschreiben!

subpolynomiell

polynomiell

superpolynomiell

Habe ich alles richtig platziert?

Ordnen

Hier geht es weiter zum Ordnen in O-Notation.