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 Definition 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!

Ordnen