4.4 Asymptotik

Anwendung von Folgen in der Informatik:
Abschätzung von Laufzeiten oder Speicherbedarf bei Algorithmen.

• Sei $(a_n)$ die Laufzeit eines Algorithmus bei Eingabegröße $n\in \mathbb{N}$.
• Der konkrete Wert von $a_n$ ist oft unerheblich – interessiert ist nur das Wachstumsverhalten der Folge (wie schnell wächst $a_n$?).

Landau-Symbole (Groß-O und Klein-o)

Wir betrachten die Menge $F_{+}:=\{(a_n)\subseteq \mathbb{R}:a_n>0\text{ für alle }n\in \mathbb{N}\}$.

Sei $(b_n)\in F_{+}$. Dann definieren wir:

• Groß-O von $b_n$:

  $$O(b_n):=\{(a_n)\in F_{+}:{\left(\frac{a_n}{b_n}\right)}_{n\in \mathbb{N}}\text{ ist beschränkt}\}$$

• Klein-o von $b_n$:

  $$o(b_n):=\{(a_n)\in F_{+}:\underset{n\to \mathrm{\infty }}{lim}\frac{a_n}{b_n}=0\}$$

• Es gilt: $o(b_n)\subseteq O(b_n)$, da jede Nullfolge beschränkt ist.

• Warnung: Das „=“ in den Definitionen ist kein echtes Gleichheitszeichen, sondern nur symbolische Schreibweise.
  → Man schreibt $a_n\in O(b_n)$ statt $a_n=O(b_n)$.

Eigenschaften der $O$- und $o$-Notation

Seien $(a_n),(b_n),(c_n),(d_n)\in F_{+}$ und $\alpha ,\beta \in {\mathbb{R}}_{+}$:

1. Wenn $a_n,b_n\in O(c_n)$, dann gilt:
   $\alpha a_n+\beta b_n\in O(c_n)$

2. Wenn $a_n\in O(b_n)$ und $c_n\in O(d_n)$, dann:
   $a_n{c}_n\in O(b_n{d}_n)$

3. Wenn $a_n\in O(b_n)$ und $b_n\in O(c_n)$, dann:
   $a_n\in O(c_n)$
   (Transitivität)

4. Es gilt:
   $a_n\in O(b_n)⟺\frac{1}{b_n}\in O\left(\frac{1}{a_n}\right)$

INFO

Alle Aussagen gelten auch mit Klein-o statt Groß-O.

Weitere Landau-Symbole: $\mathrm{\Omega }$ und $\omega$

Analog zur Definition von $O$ und $o$:

• Groß-$\mathrm{\Omega }$ von $b_n$:

  $$\mathrm{\Omega }(b_n):=\{(a_n)\in F_{+}:{\left(\frac{b_n}{a_n}\right)}_{n\in \mathbb{N}}\text{ ist beschränkt}\}$$

• Klein-$\omega$ von $b_n$:

  $$\omega (b_n):=\{(a_n)\in F_{+}:\underset{n\to \mathrm{\infty }}{lim}\frac{b_n}{a_n}=0\}$$

Beispiel

Seien:

• $a_n=2n^2+3n+1$
• $b_n=n^2$
• $c_n=n^7$

Dann gilt:

• $a_n\in O(b_n)$
• $a_n\in O(c_n)$

Denn:

$$\underset{n\to \mathrm{\infty }}{lim}\frac{a_n}{b_n}=\underset{n\to \mathrm{\infty }}{lim}\frac{2n^2+3n+1}{n^2}=\underset{n\to \mathrm{\infty }}{lim}\frac{2+\frac{3}{n}+\frac{1}{n^2}}{1}=2$$

und

$$\underset{n\to \mathrm{\infty }}{lim}\frac{a_n}{c_n}=\frac{2n^2+3n+1}{n^7}=\frac{\frac{2}{n^5}+\frac{3}{n^6}+\frac{1}{n^7}}{1}=0$$

Allgemein gilt

Ein Polynom $p(n)$ vom Grad $k$ liegt in $O(n^k)$.

Alternative Notation

Folgen kann man auch als Funktionen schreiben:

• Sei $(a_n)$ eine Folge. Dann:$$f_a(n):=a_n$$

Übersicht: Landau-Symbole und Bedeutung

Landau-Symbol	Bezeichnung	Bemerkung
$O(1)$	beschränkt
$O({\log }_a(n))$	logarithmisch	$a>1$
$O(n)$	linear
$O(n{\log }_a(n))$	„$n$ log $n$“	$a>1$
$O(n^2)$	quadratisch
$O(n^3)$	kubisch
$O(n^k)$	polynomial	$k\in {\mathbb{N}}^{\ast }$
$O(a^n)$	exponentiell	$a>1$