Kurs:Algorithmen und Datenstrukturen (hsrw)/Vorlesung/Notation Eigenschaften

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$ )

$\exists c,n_{0}\in \mathbb {N} :t(n)\leq c\cdot (f(n)+g(n))\ \forall n>n_{o}$

$\Rightarrow t(n)\leq 2\cdot c\cdot max(f(n),g(n))\ \forall n>n_{0}$

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

nun der Beweis nach links ( $\Leftarrow$ )

$\exists c,n_{0}\in \mathbb {N} :t(n)\leq c\cdot (max(f(n),g(n)))\ \forall n>n_{0}$

$\Rightarrow t(n)\leq c\cdot (f(n)+g(n))\ \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))\land g(n)\in O(f(n))$ 
3.  $O(f(n))\subset O(g(n))\ {\text{genau dann wenn }}f(n)\in O(g(n))\land 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 \exists c_{0},n_{0}\in \mathbb {N} :f(n)\leq c_{0}\cdot g(n)\ \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 \exists c_{1},n_{1}\in \mathbb {N} :t(n)\leq c_{1}\cdot f(n)\ \forall n>n_{1}$ (siehe Definition)

$\Rightarrow t(n)\leq c_{1}\cdot f(n)\leq c_{1}\cdot c_{0}\cdot g(n)\ \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))~und~g(n)\in O(h(n))$ , dann ist auch  $f(n)\in O(h(n))$ .

Beweis

$f(n)\leq c_{0}\cdot g(n)\ \forall n>n_{0}~und$

$g(n)\leq c_{1}\cdot h(n)\ \forall n>n_{1}~und$

$\Rightarrow f(n)\leq c_{0}\cdot g(n)\leq c_{0}\cdot c_{1}\cdot h(n)\ \forall n\geq 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.  $lim_{n\to \infty }(f(n)/g(n))=c,c>0\Rightarrow O(f(n))=O(g(n))$ 
2.  $lim_{n\to \infty }(f(n)/g(n))=0\Rightarrow O(f(n))\subset O(g(n))$

Ein häufiges Problem sind Grenzwerte der Art ${\frac {\infty }{\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 \infty$ 
Seien f und g auf dem Intervall  $[\alpha ,\infty )$  differenzierbar.
Es gelte  $lim_{x\to \infty }f(x)=lim_{x\to \infty }g(x)=0(bzw.=\infty )$  
und es existiere  $lim_{x\to \infty }{\frac {f'(x)}{g'(x)}}$ .
Dann existiert auch  $lim_{x\to \infty }{\frac {f(x)}{g(x)}}$  und es gilt:
 $lim_{x\to \infty }{\frac {f'(x)}{g'(x)}}=lim_{x\to \infty }{\frac {f(x)}{g(x)}}$

Beispiel

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

lim_{n\to \infty }{\frac {3n+5}{n}}\Rightarrow lim_{n\to \infty }{\frac {3}{1}}=3>0\Rightarrow O(3n+5)=O(n)

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

lim_{n\to \infty }{\frac {n^{2}+5}{n^{3}}}\Rightarrow lim_{n\to \infty }{\frac {2n}{3n^{2}}}\Rightarrow lim_{n\to \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))~und~g(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 $\exists c,n_{0},\forall n>n_{0}:s(n)\leq c\cdot n^{k}$ .

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

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

$\Rightarrow \exists n>n_{0}:und~n<1$