Ordnen

Im Video wurde die O-Notation in der Form \(f=O(g)\) benutzt. Diese Schreibweise ist eigentlich schrecklich, weil \(=\) hier kein symmetrischer Operator, also insbesondere kein Zeichen für Gleichheit ist. Leider ist diese Notation in anderen Quellen und generell der Algorithmik so verbreitet, dass auch wir sie nicht völlig umgehen können. Wir empfehlen jedoch: Gewöhnt euch von vorneherein an, \(\in\) zu verwenden und \(O(g)\) konsequent als die Menge aller Funktionen \(f\) zu sehen, die asymptotisch maximal so schnell wachsen wie \(g\).

Bisher haben wir Terme nur in drei verschiedene Kategorien sortiert. Mit der O-Notation kann man sehr viel feinere Vergleiche anstellen. Zum Beispiel: \(n\) wächst langsamer als \(n \log(n)\), welches wiederum langsamer wächst als \(n^2\). Alle diese Terme haben polynomielles Wachstum. Wir schreiben \(f \in O(g)\), falls \[ \exists c > 0 \quad \exists n_0 \geq 0 \quad \forall n\geq n_0:\quad f(n) \leq c \cdot g(n). \] Ein einfacher Weg, um zu sehen, ob \(f\in O(g)\), ist, den Grenzwert von \(f(n) / g(n)\) für \(n\) gegen \(\infty\) zu bestimmen: Wenn dieser kleiner unendlich ist, dann ist \(f\in O(g)\).

Beispiele:

1. \(f(n) = n\) und \(g(n) = n \log(n)\); es gilt $$\frac{f(n)}{g(n)} = \frac{n}{n \log(n)} = \frac{1}{\log(n)} \xrightarrow{n \rightarrow \infty} 0.$$ Also wächst \(g(n) = n\log(n)\) schneller als \(f(n) = n\).
   
   
2. \(f(n) = \log(n)\) und \(g(n) = \log(n^5)\); wir wissen, dass für alle Terme \(t\), \(\log(n^t) = t \log(n)\). Dies ist eine allgemeine Logarithmenregel. Damit haben wir $$\frac{f(n)}{g(n)} = \frac{\log(n)}{\log(n^5)} = \frac{\log(n)}{5\log(n)} = \frac{1}{5} \xrightarrow{n \rightarrow \infty} \frac{1}{5}.$$ Also wächst \(g(n) = \log(n^5)\) genau so schnell wie \(f(n) = \log(n)\) (in der O-Notation).
   
   
3. \(f(n) = 2^{2n}\) und \(g(n) = 2^{n}\); hier brauchen wir ein paar mehr Umformungsregeln für Exponentiationen. Mit diesen haben wir $$\frac{f(n)}{g(n)} = \frac{2^{2n}}{2^{n}} = 2^{2n} \cdot 2^{-n} = 2^{2n - n} = 2^n \xrightarrow{n \rightarrow \infty} \infty.$$ Also wächst \(f(n) = 2^{2n}\) schneller als \(g(n) = 2^n\).
   
   

Wie hier du sehen kannst, kann man mit Termumformungen auch ganz schnell entscheiden, wogegen ein Term konvergiert (für \(n\) gegen unendlich). Wir fassen diese drei Beispiele in O-Notation wie folgt zusammen.

1. \(n\) wächst echt langsamer als \(n \log(n)\);
2. \(\log(n)\) wächst genauso schnell wie \(\log(n^5)\);
3. \(2^{2n}\) wächst echt schneller als \(2^{n}\).

Wenn wir mehr komplizierte Beispiele klassifizieren wollen, können wir die Technik des Normalisierens benutzen. Normalisieren bedeutet einen Term in eine standardisierte Form zu transformieren; zwei Terme in derselben Form sind viel leichter zu vergleichen. Hier werden wir die Basisnormierung kennenlernen. Gegeben einen Term \(b^t\), können wir ihn durch Termumformungen in die Form \(a^s\) bringen; damit benutzen wir dann die Basis \(a\) und nicht mehr \(b\). Zwei Terme mit derselben Basis kann man leicht vergleichen, indem man die Exponenten vergleicht.

Zum Beispiel, wenn ich die zwei Terme \(2^n\) und \(\log(n)^{\log(n)}\) vergleichen möchte, kann ich das wie folgt machen. Beide Terme sind von der Form \(x\) hoch \(y\), wobei die Basis jeweils unterschiedlich ist. Der Vergleich der Terme wäre viel einfacher, wenn die Basen gleich wären; also normalisieren wir, wir benutzen Termumformungen, damit beide Terme die gleiche Basis haben. Ich wähle die Basis \(2\), da dies eine einfache Basis ist und einer der Terme dann schon normalisiert ist. Mittels Termumformungen haben wir $$ \log(n)^{\log(n)} = (2^{\log(\log(n))})^{\log(n)} = 2^{\log(\log(n)) \cdot \log(n)}. $$ Damit können wir schnell feststellen, dass dieser Term langsamer wächst als \(2^n\), da ja selbst der Exponent langsamer wächst. Damit gilt $$ \log(n)^{\log(n)} \in O(2^n). $$

Jetzt bist du wieder dran. Dies ist die abschließende Übung, in der du verschiedene Terme bezüglich ihres Wachstums sortierst, also so, dass ein Term \(f\) links von einem Term \(g\) kommt, falls \(f \in O(g)\). Verwende alle Techniken, die du hier gelernt hast und benutze wieder drag and drop um die Terme in dem freien Feld zu sortieren. Du kannst auch Stift und Papier für die Termumformungen benutzen, falls notwendig.

Andere Landau-Symbole

Zusätzlich zu dem \(O\)-Symbol gibt es noch weitere Landau-Symbole, mit denen man das Wachstum zweiter Terme vergleichen kann. \(f \in O(g)\) heißt ja, dass \(f\) höchstens so schnell wächst wie \(g\). Analog gibt es jetzt Symbole für "mindestens so schnell", "genauso schnell", "echt langsamer" und "echt schneller". Formal definieren wir dies wie folgt.

1. \(f \in \Omega(g) \Leftrightarrow \exists c > 0 \quad \exists n_0 \geq 0 \quad \forall n\geq n_0:\quad f(n) \geq c \cdot g(n)\);
2. \(f \in \Theta(g) \Leftrightarrow f \in O(g)\) und \(f \in \Omega(g)\);
3. \(f \in o(g) \Leftrightarrow \forall c > 0 \quad \exists n_0 \geq 0 \quad \forall n\geq n_0: \quad f(n) < c \cdot g(n)\);
4. \(f \in \omega(g) \Leftrightarrow \forall c > 0 \quad \exists n_0 \geq 0 \quad \forall n\geq n_0:\quad f(n) > c \cdot g(n) \).

Wir können testen, ob \(f\in o(g)\) ist, indem wir wieder den Grenzwert von \(f(n) / g(n)\) für \(n\) gegen \(\infty\) bestimmen: Wenn dieser \(0\) ist, dann gilt \(f\in o(g)\).

Zwischen den verschiedenen Landau-Symbolen gibt es natürlich viele Zusammenhänge. Zum Beispiel sind \(f \in \Omega(g)\) und \(g \in O(f)\) äquivalent; ebenso ist \(f \in \omega(g)\) äquivalent zu \(g \in o(f)\)

Was haben wir gelernt?

1. Termumformungen verraten viel über einen Term.
2. Kategorisieren gibt ein grobes Bild.
3. Für sehr unterschiedliche Terme hilft Normalisieren.
4. Weitere Landau-Symbole geben mehr Vergleichsmöglichkeiten.