Matthäus Gdaniec

Beispiele

In den folgenden Beispielen ist $f=f(x)$ stets als Funktion von $x$ zu verstehen.

Notation	Bedeutung	Anschauliche Erklärung	Beispiele für Laufzeiten
$f\in {\mathcal {O}}(1)$	$f$ ist konstant	$f$ wächst nicht, wenn sich das Argument ändert.
$f\in {\mathcal {O}}(\log x)$	$f$ logarithmisches Wachstum	$f$ wächst ungefähr um einen konstanten Betrag, wenn sich das Argument verdoppelt. Merke: Die Basis des Logarithmus ist egal.	Binäre Suche im sortierten Feld mit x Einträgen
$f\in {\mathcal {O}}({\sqrt {x}})$	$f$ Wachstum wie die Wurzelfunktion	$f$ wächst ungefähr auf das doppelte, wenn sich das Argument vervierfacht
$f\in {\mathcal {O}}(x)$	$f$ lineares Wachstum	$f$ wächst ungefähr auf das doppelte, wenn sich das Argument verdoppelt.	Suche im unsortierten Feld mit x Einträgen
$f\in {\mathcal {O}}(x\log x)$			Suche im sortierten Feld mit x Einträgen Mergesort
$f\in {\mathcal {O}}(x^{2})$	$f$ quadratisches Wachstum	$f$ wächst ungefähr auf das vierfache, wenn sich das Argument verdoppelt	Einfache Algorithmen zum Sortieren von x Zahlen Bubblesort
$f\in {\mathcal {O}}(2^{x})$	$f$ exponentielles Wachstum	$f$ wächst ungefähr auf das doppelte, wenn sich das Argument um eins erhöht
$f\in {\mathcal {O}}(x!)$	$f$ faktorielles Wachstum	$f$ wächst ungefähr um das $x$-fache, wenn sich das Argument von $x-1$ auf $x$ erhöht.

Rechenbeispiele

Zu der ${\mathcal {O}}$ Notation (Obereren Schranke)

Das Wachstum eines Polynoms $f(x)=\sum _{i=0}^{n}k_{i}\cdot x^{i}$ ist nach ${\mathcal {O}}$-Notation beschränkt durch das Monom mit dem größten Grad, also durch ${\mathcal {O}}(x^{n})$.

$f(x)={\mathcal {O}}(x^{n})\,\,\,\forall n\geq n_{0}$

${\mathcal {O}}(g(x))=c\cdot g(x)$

$\Leftrightarrow \,\,\,\,\,\,f(x)\leq c\cdot g(x)\,\,\,\forall n\geq n_{0}$

Gegeben sei eine Funktion $f(x)$ mit $f(x)=3x^{3}-2x^{2}+x-9$

$f(x)={\mathcal {O}}(x^{3})\,\,\,\forall n\geq n_{0}$

$3x^{3}+2x^{2}+x+9\leq c\cdot x^{3}\,\,\,\forall n\geq n_{0}$

Wahl c & $n_{0}$:

Das Monom mit größten Grad der Funktion $f(x)=3x^{3}-2x^{2}+x-9$ ist $x^{3}$

$\rightarrow \,\,\,\,\,c\leq 3$

Graphen

wähle $c=15\,\,\,\,n_{0}=1$ ( beide Werte zufällig gewählt )

Beweis:

$3x^{3}+2x^{2}+x+9\leq 15\cdot x^{3}\,\,\,\forall n\geq n_{0}$

$\Leftrightarrow 2x^{2}+x+9\leq 12\cdot x^{3}\,\,\,\forall n\geq n_{0}$

$\Leftrightarrow 2x^{2}+x+9\leq 12\cdot x^{3}\,\,\,\forall n\geq n_{0}$

$\Leftrightarrow {2 \over x}+{1 \over x^{2}}+{9 \over x^{3}}\leq 12\,\,\,\forall n\geq n_{0}$

Da $n_{0}=1$

${2 \over 1}+{1 \over 1^{2}}+{9 \over 1^{3}}\leq 12$

$\Leftrightarrow 12\leq 12$

q.e.d.

TEST

Das Wachstum eines Polynoms $f(x)=\sum _{i=0}^{n}k_{i}\cdot x^{i}$ ist nach ${\mathcal {O}}$-Notation beschränkt durch das Monom mit dem größten Grad, also durch ${\mathcal {O}}(x^{n})$.

$f(x)={\mathcal {O}}(x^{3})$

$f(x)\leq c\cdot g(x)\,\,\,\forall n\geq n_{0}$

${2 \over x}+{1 \over x^{2}}+\cdots \leq 12$