291026 Vorlesung

$a_n={\left(1+\frac{1}{n}\right)}^n$ $b_n={\left(1+\frac{1}{n}\right)}^{n+1}e={\lim }_{n\to \infty }{a}_n$

$a_n={\left(1+\frac{a}{x_n}\right)}^{x_n}⟶e^a$ $x_n⟶\pm \infty$

${\left(\frac{n+7}{n-2}\right)}^n={\left(\frac{n\cdot \left(1+\frac{7}{n}\right)}{n\cdot \left(1-\frac{2}{n}\right)}\right)}^n=\frac{{\left(1+\frac{7}{n}\right)}^n}{{\left(1-\frac{2}{n}\right)}^n}⟶\frac{e^7}{e^{-2}}=e^9$

weiter mit Landau

$T(n)=3\underset{\text{wichtig}}{\underbrace{n^2}}-27n^2+\lg n+7$

2. Die Groß O Notation

Für Folge $f:\mathbb{N}\to \mathbb{R}$ definiert man die Klasse $O(f)$

$\underset{\text{Funktionen (Folgen)}}{\underbrace{O(f)}}=\{g:\mathbb{N}\to \mathbb{R}\mid \exists c>0\exists n_0\forall n>n_0:|g(n)|\le c\cdot |f(n)|\}$ die sich durch f nach oben beschränken lassen

(Skizze auf Seite 1: Kurven $y=g(n)$, $y=f(n)$, $y=c\cdot f(n)$, Stelle $n_0$)

Bemerkung: eigentlich statt $g\in O(f)$ schreibt man auch $g=O(f)$ oder $g(n)=O(f(n))$ > g(n) ist groß O von f(n)

Kriterium:

K1 Ist ${\lim }_{n\to \infty }\frac{g(n)}{f(n)}=a\in \mathbb{R}$ dann ist $g(n)=O(f(n))$

K2 Ist ${\lim }_{n\to \infty }\frac{g(n)}{f(n)}=\pm \infty$ dann ist $g(n)\ne O(f(n))$

Beweis von K1

${\lim }_{n\to \infty }\frac{g(n)}{f(n)}=a$ $⟹{\lim }_{n\to \infty }\frac{|g(n)|}{|f(n)|}=|a|$ $\forall ϵ>0\exists n_0\forall n>n_0$ $\left|\frac{|g(n)|}{|f(n)|}-|a|\right|<ϵ$ $⟹\frac{|g(n)|}{|f(n)|}-|a|<ϵ$ $⟹\frac{|g(n)|}{|f(n)|}<ϵ+|a||\cdot |f(n)|$ $|g(n)|<(ϵ+|a|)\cdot |f(n)|$ $⟹g(n)=O(f(n))$

Beweis von K2

Vor. ${\lim }_{n\to \infty }\frac{g(n)}{f(n)}=\pm \infty$ $⟹{\lim }_{n\to \infty }\frac{|g(n)|}{|f(n)|}=\infty$ Beh: $g(n)\ne O(f(n))$ Bew. z.z. $\forall c>0\forall n_0\exists n>n_0:|g(n)|>c|f(n)|$

$\forall S\exists n_0\forall n>n_0:\left|\frac{g(n)}{f(n)}\right|>S$ $\left({\lim }_{n\to \infty }\frac{g(n)}{f(n)}=\infty \right)$ $c=S$ $\forall c>0\forall n_0\exists n>n_0:\frac{g(n)}{f(n)}>c$ $:|g(n)|>c|f(n)|$

Beispiele:

a) $5n^3-7n^2+70=O(n^3)$ ${\lim }_{n\to \infty }\frac{5n^3-7n^2+70}{n^3}={\lim }_{n\to \infty }5-\frac{7}{n}+\frac{70}{n^3}=5\in \mathbb{R}$ $\stackrel{K1}{\Rightarrow }5n^3-7n^2+70=O(n^3)$

b) $n^3=O(5n^3-7n^2+70)$ da ${\lim }_{n\to \infty }\frac{n^3}{5n^3-7n^2+70}=\frac{1}{5}\in \mathbb{R}$

c) $n^2=O(n^3)$ da ${\lim }_{n\to \infty }\frac{n^2}{n^3}={\lim }_{n\to \infty }\frac{1}{n}=0\in \mathbb{R}$

d) $n^3\ne O(n^2)$ da ${\lim }_{n\to \infty }\frac{n^3}{n^2}=\infty$

e) $g(n)=O(1)⟺\exists c\exists n_0\stackrel{\text{Fast alle}}{\overbrace{\forall n>n_0}}:|g(n)|\le c$ $⟺\exists d>0\forall n:|g(n)|\le d$ $⟺g(n)$ ist beschränkt

Rechenregeln

R1: $\begin{array}{c}{g}_1(n)=O(f_1(n))\\ g_2(n)=O(f_2(n))\end{array}\}⟹\begin{array}{c}{g}_1(n)+g_2(n)=O(\max \{f_1,f_2\})\\ g_1(n)\cdot g_2(n)=O(f_1(n)\cdot f_2(n))\end{array}$

R2: $c\cdot f(n)=O(f(n))$

R3: $h(n)=O(g(n)),g(n)=O(f(n))$ dann ist $h(n)=O(f(n))$

R4: $g(n)=O(f(n))⟺O(g(n))\subseteq O(f(n))$

Beweis zu R3

$\exists c_1\exists n_1\forall n>n_1:|h(n)|\le c_1|g(n)|$ $\exists c_2\exists n_2\forall n>n_2:|g(n)|\le c_2|f(n)|$ $\exists c_3\underset{n_3=\max \{n_1,n_2\}}{\underbrace{\exists n_3}}\forall n>n_3:|h(n)|\le \underset{c_3}{\underbrace{c_1{c}_2}}|f(n)|$

Beispiel:

$g(n)=5n\cdot g_1(n)+(n-1)\cdot g_2(n)$

Dann gilt: $g_1(n)=O(n)g_2(n)=O(n^2)$ $g(n)=5n\cdot O(1)+(n-1)\cdot O(n^2)$ $\stackrel{5n=O(n),n-1=O(n)}{=}O(n)\cdot O(n)+O(n)\cdot O(n^2)$ $\stackrel{R1}{=}O(n^2)+O(n^3)$ $\stackrel{R1}{=}O(n^3)$

Achtung

Ist $g(n)=O(n)$ so ist $g(n)=O(n^2)$ da $O(n)\subseteq O(n^2)$ Es gilt aber nicht $O(n^2)=O(n)$ weil $O(n^2)⊈O(n)$ $n^2\ne O(n)$

Laufzeiten:

$g(n)=$	Laufzeit
$O(1)$	konstant 🙂
$O({\log }_{a}n)$	Logarithmisch $(a>1)$
$O(n)$	Linear
$O(n\log n)$	überlinear
$O(n^2)$	Quadratisch
$O(n^k)$	Polynomial
$O(a^n)$	Exponentiell ☹️

${\log }_{a}n=\frac{{\log }_{b}n}{{\log }_{b}a}=\underset{c}{\underbrace{\frac{1}{{\log }_{b}a}}}\cdot {\log }_{b}n$

$O(1)\subset O(\log n)\subset O(n\log n)\subset O(n^2)\subset O(n^k)\subseteq {\bigcup }_{k=1}^{\infty }O(n^k)\subset O(a^n)\subset O(n!)\subset O(n^n)$

3. Weitere Landau-Symbole

a) $\Omega (f)=\{g:\mathbb{N}\to \mathbb{R}\mid f\in O(g)\}$ Groß-Omega b) $\Theta (f)=O(f)\cap \Omega (f)$ Groß-Teta c) $o(f)=\left\{g:\mathbb{N}\to \mathbb{R}\mid {\lim }_{n\to \infty }\frac{g(n)}{f(n)}=0\right\}$ klein-O d) $\omega (f)=\{g:\mathbb{N}\to \mathbb{R}\mid f=o(g)\}$ klein-Omega e) $g\sim f⟺{\lim }_{n\to \infty }\frac{g(n)}{f(n)}=1$ Schlange g und f sind asymptotisch gleich

Bemerkung Statt $g\in \Omega (f)g\in o(f)$ schreibt man wieder $g=\Omega (f)g=o(f)$

Kriterium

K3 $g(n)=\Omega (f(n))⟺f(n)=O(g(n))$ K4 $g(n)=\Theta (f(n))⟺g(n)=O(f(n)),f(n)=O(g(n))$ K5 ${\lim }_{n\to \infty }\frac{|g(n)|}{|f(n)|}=\{\begin{array}{cc}0& g=o(f),f\omega (g),g=O(f)f=\Omega (g)g\ne \Theta (f)\\ a>0& g=O(f),f=O(g),g=\Omega (f),f=\Omega (g),g=\Theta (f)\\ \infty & f=o(g),g=\omega (f),f=O(g),g=\Omega (f)\end{array}$

Beispiel:

Ist p Polynom vom Grad k, d.h. … so gilt $p(n)=\Theta (n^k)$, d.h. $p(n)=O(n^k)$ und $n^k=O(p(n))$ Insbesondere ist $O(p(n))=O(n^k)$ $p(n)=a_k{n}^k+a_{k-1}{n}^{k-1}+\cdots +a_0{n}^0$ $⟹{\lim }_{n\to \infty }\frac{p(n)}{n^k}={\lim }_{n\to \infty }{a}_k+\frac{a_{k-1}}{n}+\frac{a_{k-2}}{n^2}+\cdots +\frac{a_0}{n^k}=a_k\ne 0$ $⟹{\lim }_{n\to \infty }\frac{|p(n)|}{n^k}=|a_k|>0$ $\stackrel{K5}{\Rightarrow }p(n)=\Theta (n^k)$

Regeln:

K6 $g(n)=o(f(n))\stackrel{K1}{\Rightarrow }g(n)=O(f(n))$ K7 $g(n)\sim f(n)\stackrel{K5}{\Rightarrow }g(n)=\Theta (f(n))$

(Skizze auf Seite 4: Rechteck „alle Folgen $f:\mathbb{N}\to \mathbb{R}$“ mit den Mengen $\omega (f)$, $\Theta (f)$, $o(f)$, $O(f)$, $\Omega (f)$ und Fragezeichen)

4. Stirlingsche Formel

a) $n!\sim \sqrt{2\pi n}\cdot {\left(\frac{n}{e}\right)}^n$ b) $n!=\sqrt{2\pi n}\cdot {\left(\frac{n}{e}\right)}^n\cdot \left(1+\frac{1}{12n}+O\left(\frac{1}{n^2}\right)\right)$