Wieder mal Zeit für ein Einschubkapitel, das nicht so richtig in den Ablauf reinpasst. Heute auf dem Menü: die Landau’sche Notation zur Abschätzung von Laufzeit- und Speicherkomplexität.
Im folgenden Kapitel betrachten wir zunächst die Funktion
$$ f:\mathbb{N}\to\mathbb{R},\quad f(n)=23n^5-2n^2+13. $$Die Landau-Notation beschreibt das Wachstumsverhalten von Funktionen. Dabei interessiert uns, wie sich eine Funktion bei immer größeren Eingabewerte verhält.
Das ist beispielsweise in der Informatik ganz praktisch, wenn wir die Laufzeit eines Algorithmus untersuchen. Uns interessiert weniger, ob ein Algorithmus für die Eingabe 10 genau 3 oder 4 Millisekunden benötigt, sondern eher, wie sich die Laufzeit bei immer größeren Eingaben entwickelt. Grundsätzlich unterscheiden wir fünf Notationen.
$f$ wächst höchstens so schnell wie $g$ / $g$ ist eine obere Schranke für $f$.
Um eine Funktion zu finden, die $f$ nach oben beschränkt, entfernen wir zunächst alle negativen nicht-dominanten Terme und klammern anschließend das dominante Polynom aus. Das dominante Polynom ist dabei der Term, der das Wachstum der Funktion für große $n$ bestimmt.
$$ \begin{aligned} f(n)&=23n^5-2n^2+13\\ &\le 23n^5+13\\ &=n^5\left(23+\frac{13}{n^5}\right)\\ &\le n^5(23+13)\\ &=36n^5. \end{aligned} $$Damit haben wir eine obere Schranke gefunden:
$$ f\in\mathcal{O}(n^5) $$mit $c=36$ und $n_0=1$.
Um $n_0$ zu bestimmen, müssen wir die Ungleichung aus der Definition erfüllen:
$$ 23n^5-2n^2+13\le 36n^5. $$Für $n\ge 1$ ist das erfüllt. Damit haben wir sowohl eine geeignete Konstante $c$ als auch ein geeignetes $n_0$ gefunden.
$f$ wächst mindestens so schnell wie $g$ / $g$ ist eine untere Schranke für $f$.
Während wir bei der Groß-O-Notation eine obere Schranke suchen, suchen wir bei Groß-$\Omega$ entsprechend eine untere Schranke.
Für unsere Funktion können wir beispielsweise die negativen Terme ignorieren:
$$ \begin{aligned} f(n)&=23n^5-2n^2+13\\ &\ge 23n^5-2n^2\\ &=n^5\left(23-\frac{2}{n^3}\right)\\ &\ge n^5(23-2)\\ &\ge 21n^5. \end{aligned} $$Damit gilt:
$$ f\in\Omega(n^5) $$mit $c=21$ und $n_0=1$.
$f$ wächst genauso schnell wie $g$.
Das bedeutet, dass wir sowohl eine obere als auch eine untere Schranke gefunden haben.
Da unsere Funktion sowohl in $\mathcal{O}(n^5)$ als auch in $\Omega(n^5)$ liegt, folgt:
$$ f\in\Theta(n^5). $$$f$ wächst langsamer als $g$.
Im Gegensatz zur Groß-O-Notation muss die Ungleichung hier für alle $c>0$ irgendwann (ab $n_0$) erfüllt sein.
$f$ wächst schneller als $g$.
Hier gilt das Gegenteil der klein-o-Notation: Egal wie groß wir $c$ wählen, muss $f$ irgendwann schneller als das $c$-fache von $g$ wachsen.
1. $2n^2-8n\in\mathcal{O}(n^2)$
Wir suchen eine obere Schranke für die Funktion:
$$ \begin{aligned} 2n^2-8n&\le 2n^2 \\ c&=2 \end{aligned} $$Das ist für alle $n\in\mathbb{N}$ erfüllt, da $-8n$ immer negativ ist.
Damit gilt:
$$ 2n^2-8n\in\mathcal{O}(n^2) $$mit $c=2$ und $n_0=1$.
Falls wir doch ein $n_0$ bräuchten, wäre hier jetzt der Punkt die Ungleichung $f(n)\le c\cdot g(n)$ nach $n$ umzustellen. Das Ergebnis wäre dann unser $n_0$.
2. $n!\in\mathcal{O}(n^n)$
Da jeder einzelne Faktor höchstens $n$ groß ist, können wir jeden Faktor durch $n$ nach oben abschätzen:
$$ \begin{aligned} n!&=1\cdot2\cdot3\cdot\dots\cdot(n-1)\cdot n\\ &\le\underbrace{n\cdot n\cdot n\cdot\dots\cdot n}_{n-\text{mal}}\\ &=n^n. \end{aligned} $$Damit gilt:
$$ n!\in\mathcal{O}(n^n) $$mit $c=1$ und $n_0=1$.
3. $\frac{n^2+3}{n^{3/2}}\in o(n)$
Hier müssen wir zeigen, dass die Funktion langsamer wächst als $n$. Außerdem in der Aufgabenstellung enthalten: $n\ge3$.
$$ \begin{aligned} \frac{n^2+3}{n^{3/2}}&\le cn \\ n^2+3&\le cn^{\frac52} \\ 3&\le cn^{\frac52}-n^2=n^2\left(cn^{\frac12}-1\right) \\ &=n^2(c\sqrt n-1)\quad\mid* \\ 3&\le 9(c\sqrt n-1) \end{aligned} $$* Anmerkung: Wir versuchen ja gerade ein $n_0$ zu finden das die gesamte Ungleichung erfüllt. Dazu können wir alle möglichen $n$, bis auf eines, gleich 3 setzen. Im Umkehrschluss heißt das, wir müssen die Ungleichung jetzt nur noch für ein $n$ lösen.
Damit der gesamte rechte Teil der Ungleichung nicht kleiner als 3 wird, muss der Klammerausdruck zwangsweise größer als $\frac13$ sein:
$$ \begin{aligned} \frac13&\le c\sqrt n-1 \\ \frac4{3c}&\le\sqrt n \\ \frac{16}{9c^2}&\le n \end{aligned} $$Wähle $n_0\ge\lceil\frac{16}{9c^2}\rceil$, da $c\ge1\in\mathbb{N}$ gilt
$$\frac{n^2+3}{n^{3/2}}\in o(n).$$4. $\ln(n)\in\omega(1)$
Hier sollen wir zeigen, dass der natürliche Logarithmus schneller wächst als die konstante Funktion $g(n)=1$.
Dazu können wir die Ungleichung nach $n$ umformen:
$$ \begin{aligned} \ln(n)&>c\\ n&>e^c. \end{aligned} $$Wähle $n_0>\lceil e^c\rceil$, da $c\ge1\in\mathbb{N} gilt$
$$ \ln(n)\in\omega(1). $$Last edited: 19.11.2026