Kurs:Algorithmen und Datenstrukturen/Vorlesung/Notation Eigenschaften

Startseite

Vorlesung

1.Einleitung

2. Theoretische Grundlagen

2.1 Programmierparadigmen

2.2. Laufzeitanalysen

2.3. Entwurfsmuster

3. Suchen

3.1 Suchen in sortierten Folgen

3.2 Suchen in Texten

4. Sortieren

4.1 Algorithmen für vergleichsbasiertes Sortieren

4.2 Weitere Sortierprobleme

5. Dynamische Datenstrukturen

5.1 Binäre Suchbäume

5.2 AVL Bäume

5.3 2-3-4-Bäume und Rot-Schwarz Bäume

5.4 Heaps

5.5 Hashtabellen

6. Graphen

6.1 Einführung

6.2 Breitensuche

6.3 Tiefensuche

6.4 Topologisches Sortieren

6.5 Berechnung kürzester Wege

6.6 Berechnung maximaler Flüsse

6.7 Spannbäume

7. Optimierung

7.1 Grundlagen

7.2 Kombinatorische Optimierung

7.4 Lineare Optimierung

7.5 Simplex Verfahren

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$