Kurs:Algorithmen und Datenstrukturen/Vorlesung/Notation Eigenschaften

Lemma

Für beliebige Funktionen f,g gilt:
$O(f(n)+g(n))=O(max(f(n),g(n))$

Beweis in beide Richtungen

$t(n)\in O(f(n)+g(n))\Rightarrow t(n)\in O(max(f(n),g(n)))$

$t(n)\in O(f(n)+g(n))\Leftarrow t(n)\in O(max(f(n),g(n)))$

Als erstes machen wir den Beweis nach rechts ($\Rightarrow$)

$\mathrm{\exists }c,n_0\in \mathbb{N}:t(n)\le c\cdot (f(n)+g(n))\mathrm{\forall }n>n_o$

$\Rightarrow t(n)\le 2\cdot c\cdot max(f(n),g(n))\mathrm{\forall }n>n_0$

$\Rightarrow t(n)\in O(max(f(n)),g(n)))$

nun der Beweis nach links ($\Leftarrow$)

$\mathrm{\exists }c,n_0\in \mathbb{N}:t(n)\le c\cdot (max(f(n),g(n)))\mathrm{\forall }n>n_0$

$\Rightarrow t(n)\le c\cdot (f(n)+g(n))\mathrm{\forall }n>n_0$

$\Rightarrow t(n)\in O(f(n),g(n))$

Beispiel

$O(n^4+n^2)=O(n^4)$

$O(n^4+4\cdot n^3)=O(n^4)$

$O(n^4+2^n)=O(2^n)$

Lemma

1. $O(f(n))\subseteq O(g(n))\text{genau dann wenn }f(n)\in O(g(n))$
2. $O(f(n))=O(g(n))\text{genau dann wenn }f(n)\in O(g(n))\wedge g(n)\in O(f(n))$
3. $O(f(n))\subset O(g(n))\text{genau dann wenn }f(n)\in O(g(n))\wedge g(n)\notin O(f(n))$

Beweis in beide Richtungen

Beweis zu 1. nach rechts ($\Rightarrow$)

$O(f(n))\subseteq O(g(n))\Rightarrow f(n)\in O(g(n))$

$f(n)\in O(f(n))\subseteq O(g(n))\Rightarrow f(n)\in O(g(n))$

Beweis zu 1. nach links ($\Leftarrow$)

$O(f(n))\subseteq O(g(n))\Leftarrow f(n)\in O(g(n))$

$f(n)\in O(g(n))\Rightarrow \mathrm{\exists }{c}_0,n_0\in \mathbb{N}:f(n)\le c_0\cdot g(n)\mathrm{\forall }n>n_0$ (siehe Definition)

und sei t(n) ein beliebiges Element der Menge O(f(n))

$t(n)\in O(f(n))\Rightarrow \mathrm{\exists }{c}_1,n_1\in \mathbb{N}:t(n)\le c_1\cdot f(n)\mathrm{\forall }n>n_1$ (siehe Definition)

$\Rightarrow t(n)\le c_1\cdot f(n)\le c_1\cdot c_0\cdot g(n)\mathrm{\forall }n>max(n_0,n_1)$

$t(n)\in O(f(n))\Rightarrow t(n)\in O(g(n))$

$O(f(n))\subseteq O(g(n))$ (Definition der Teilmenge, da t(n) ein beliebiges Element ist)

Beispiele

$O(n^2)=\{n^2,2n^2-6,3n^2+5,\frac{1}{2}{n}^2+8,...\}$

Damit ist

$(3n^2+5)\in O(n^2)$

$O(3n^2+5)\subseteq O(n^2)$

$O(3n^2+5)=\{n^2,2n^2-6,3n^2+5,\frac{1}{2}{n}^2+8,...\}$

Damit ist

$n^2\in O(3n^2+5)$

$O(n^2)\subseteq O(3n^2+5)$

Damit ist

$O(n^2)=O(3n^2+5)$

Lemma

Falls $f(n)\in O(g(n))undg(n)\in O(h(n))$, dann ist auch $f(n)\in O(h(n))$. 

Beweis

$f(n)\le c_0\cdot g(n)\mathrm{\forall }n>n_{0}und$

$g(n)\le c_1\cdot h(n)\mathrm{\forall }n>n_{1}und$

$\Rightarrow f(n)\le c_0\cdot g(n)\le c_0\cdot c_1\cdot h(n)\mathrm{\forall }n\ge max(n_0,n_1)$

Dabei ist $c_0\cdot c_1$ eine Konstante.

Beispiel

$O(n^2)=O(3n^2)=O(\frac{1}{2}{n}^2)$

$O(n^2)\subseteq O(3n^2)\subseteq O(\frac{1}{2}{n}^2)$

$O(n^2)\subseteq O(n^{2,5})\subseteq O(n^3)$

$O(n^2)\subset O(n^{2,5})\subset O(n^3)$

Lemma

1. $li{m}_{n\to \mathrm{\infty }}(f(n)/g(n))=c,c>0\Rightarrow O(f(n))=O(g(n))$
2. $li{m}_{n\to \mathrm{\infty }}(f(n)/g(n))=0\Rightarrow O(f(n))\subset O(g(n))$

Ein häufiges Problem sind Grenzwerte der Art $\frac{\mathrm{\infty }}{\mathrm{\infty }}$ oder $\frac{0}{0}$ Bei diesem Problem kann man als Ansatz die Regel von de l'Hospital verwenden.

Satz(Regel von de L'Hospital) $x\to \mathrm{\infty }$
Seien f und g auf dem Intervall $[\alpha ,\mathrm{\infty })$ differenzierbar.
Es gelte $li{m}_{x\to \mathrm{\infty }}f(x)=li{m}_{x\to \mathrm{\infty }}g(x)=0(bzw.=\mathrm{\infty })$ 
und es existiere $li{m}_{x\to \mathrm{\infty }}\frac{f^{\prime }(x)}{g^{\prime }(x)}$.
Dann existiert auch $li{m}_{x\to \mathrm{\infty }}\frac{f(x)}{g(x)}$ und es gilt:
$li{m}_{x\to \mathrm{\infty }}\frac{f^{\prime }(x)}{g^{\prime }(x)}=li{m}_{x\to \mathrm{\infty }}\frac{f(x)}{g(x)}$

Beispiel

1. $f(n)=3n+5,g(n)=n$

$li{m}_{n\to \mathrm{\infty }}\frac{3n+5}{n}\Rightarrow li{m}_{n\to \mathrm{\infty }}\frac{3}{1}=3>0\Rightarrow O(3n+5)=O(n)$

2. $f(n)=n^2+5,g(n)=n^3$

$li{m}_{n\to \mathrm{\infty }}\frac{n^2+5}{n^3}\Rightarrow li{m}_{n\to \mathrm{\infty }}\frac{2n}{3n^2}\Rightarrow li{m}_{n\to \mathrm{\infty }}\frac{2}{6n}=0\Rightarrow O(n^2+5)\subset O(n^3)$

Beim zweiten Beispiel musste die Regel von de l'Hospital wiederholt angewandt werden.

Lemma

Gibt es immer eine Ordnung zwischen den Funktionen? Es gibt Funktionen f und g mit $f(n)\notin O(g(n))undg(n)\notin O(f(n))$. Ein Beispiel sind die Funktionen sin(n) und cos(n).

Für alle $m\in \mathbb{N}gilt:O(n^m)\subseteq O(n^{m+1})$

Beweis durch Widerspruch

Wir nehmen an, dass $s(n)\in O(n^k)$,

das heißt $\mathrm{\exists }c,n_0,\mathrm{\forall }n>n_0:s(n)\le c\cdot n^k$.

Aber es muss auch $s(n)\notin O(n^{k+1})$ gelten,

das heißt $\mathrm{\exists }n>n_0:s(n)>c\cdot n^{k+1}$

$\Rightarrow \mathrm{\exists }n>n_0:undn<1$