07 Landau-Symbolik

7. Landau-Symbolik

Voraussetzung: 04 Grenzwert und Konvergenz von Folgen (fast alle $n$, Grenzwerte, $\pm \infty$), 05 Monotonie und Beschränktheit (beschränkte Folgen)

Worum geht es?

Landau-Symbole beschreiben, wie schnell eine Folge wächst, ohne sich um Vorfaktoren und kleine $n$ zu kümmern. In der Informatik ist das die Sprache der Laufzeitanalyse: „Der Algorithmus ist $O(n\log n)$.“

7.1 Anwendungsbereiche

1. Laufzeitanalyse von Algorithmen: $T(n)$ = Anzahl der Rechenschritte bei Eingabe der Größe $n$, also $T:\mathbb{N}\to \mathbb{R}$.
2. Asymptotisches Verhalten von Folgen $a:\mathbb{N}\to \mathbb{R}$, d.h. das Verhalten für $n\to \infty$.

7.2 Einleitende Beispiele

Wachstumsvergleich (26.10.): $T_1=2,79n^2,T_2=10000n,T_3=50n\log n,T_4=n!,T_5=1,01^n,T_6=n^n$ $T_2<T_3<T_1<T_5<T_4<T_6(\text{fu¨r große }n)$

Was ist „wichtig“? (29.10.): $T(n)=3n^2-27n^2+\lg n+7$ Für das Wachstum zählt nur der $n^2$-Anteil: $\lg n$ und $7$ wachsen langsamer und werden für große $n$ bedeutungslos, die Vorfaktoren ändern nur die Konstante.

Zentrale Einsicht

$T_2=10000n$ ist für kleine $n$ größer als $T_1=2,79n^2$. Ab $n\approx 3600$ dreht sich das um, und das zählt. Wie beim Grenzwert interessiert nur, was für fast alle $n$ passiert (alle bis auf endlich viele).

---

7.3 Die Groß-O-Notation

Definition: $O(f)$

Für eine Folge $f:\mathbb{N}\to \mathbb{R}$ definiert man die Klasse $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)|\}$ Das sind alle Folgen, die sich (ab einem $n_0$, bis auf einen konstanten Faktor $c$) durch $f$ nach oben beschränken lassen.

Bild dazu: Ab $n_0$ liegt $|g(n)|$ immer unter der hochskalierten Kurve $c\cdot |f(n)|$. Vor $n_0$ darf $g$ machen, was es will. (Skizze: Mitschrift S. 1)

Schreibweise

Statt $g\in O(f)$ schreibt man auch $g=O(f)\text{oder}g(n)=O(f(n))$ gelesen: „$g(n)$ ist groß O von $f(n)$“.

Fallstrick: Das „=“ ist keine Gleichheit

$g=O(f)$ heißt $g\in O(f)$. Es ist nicht symmetrisch: $n=O(n^2)$ stimmt, aber $n^2=O(n)$ ist falsch. Lies „$=O(\dots )$“ immer als „ist in“.

7.4 Kriterien über Grenzwerte (K1, K2)

Statt mit $c$ und $n_0$ zu hantieren, prüft man meist den Grenzwert des Quotienten:

K1

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

K2

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

Beweis von K1: Aus $\lim \frac{g(n)}{f(n)}=a$ folgt $\lim \frac{|g(n)|}{|f(n)|}=|a|$. Nach Grenzwertdefinition gilt also $\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)|<\underset{=:c}{\underbrace{(ϵ+|a|)}}\cdot |f(n)|⟹g(n)=O(f(n))$ (Man kann z.B. $ϵ=1$ nehmen, dann ist $c=1+|a|$.) ∎

Beweis von K2:

• Vor.: $\lim \frac{g(n)}{f(n)}=\pm \infty$, also $\lim \frac{|g(n)|}{|f(n)|}=\infty$, d.h. $\forall S\exists n_0\forall n>n_0:\left|\frac{g(n)}{f(n)}\right|>S$.
• Beh.: $g(n)\ne O(f(n))$.
• Bew.: Zu zeigen ist die Negation der Definition: $\forall c>0\forall n_0\exists n>n_0:|g(n)|>c|f(n)|$. Sei $c>0$ und $n_0$ beliebig. Wähle in der Voraussetzung $S=c$. Dann gilt ab einem $n_1$ für alle $n>n_1$: $\frac{|g(n)|}{|f(n)|}>c$, also $|g(n)|>c|f(n)|$. Insbesondere gibt es so ein $n>n_0$ (nimm $n>\max \{n_0,n_1\}$). ∎

Wie man die Negation bildet

Die Definition hat die Form $\exists c\exists n_0\forall n:\cdots \le \dots$. Mit dem großen De Morgan (siehe GDS: Quantoren) wird daraus $\forall c\forall n_0\exists n:\cdots >\dots$. Genau das steht in „Bew. z.z.“.

Ergänzung (nicht aus der Mitschrift)

• Für die Kriterien braucht man $f(n)\ne 0$ für fast alle $n$, sonst ist der Quotient nicht definiert.
• K1 geht nur in eine Richtung: Es gibt $g=O(f)$, bei denen der Grenzwert gar nicht existiert, z.B. $g(n)=n(2+(-1{)}^n)$ und $f(n)=n$. Der Quotient springt zwischen 1 und 3 hin und her, trotzdem ist $|g(n)|\le 3|f(n)|$.

7.5 Beispiele

	Aussage	Begründung
a)	$5n^3-7n^2+70=O(n^3)$	$\lim \frac{5n^3-7n^2+70}{n^3}=\lim \left(5-\frac{7}{n}+\frac{70}{n^3}\right)=5\in \mathbb{R}$ → K1
b)	$n^3=O(5n^3-7n^2+70)$	$\lim \frac{n^3}{5n^3-7n^2+70}=\frac{1}{5}\in \mathbb{R}$ → K1
c)	$n^2=O(n^3)$	$\lim \frac{n^2}{n^3}=\lim \frac{1}{n}=0\in \mathbb{R}$ → K1
d)	$n^3\ne O(n^2)$	$\lim \frac{n^3}{n^2}=\infty$ → K2

a) und b) zusammen zeigen: $5n^3-7n^2+70$ und $n^3$ wachsen „gleich schnell“. Das wird später $\Theta$ heißen (7.9).

e) $O(1)$ = beschränkte Folgen: $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\text{ ist beschra¨nkt}$

Warum darf man in e) das $n_0$ einfach weglassen?

Vor $n_0$ gibt es nur endlich viele Folgenglieder $g(1),\dots ,g(n_0)$. Nimm $d=\max \{c,|g(1)|,\dots ,|g(n_0)|\}$, dann gilt $|g(n)|\le d$ für alle $n$. Derselbe Trick wie beim Beweis „konvergent ⟹ beschränkt“ in 05 Monotonie und Beschränktheit.

7.6 Rechenregeln (R1–R4)

Rechenregeln

• R1: Ist $g_1(n)=O(f_1(n))$ und $g_2(n)=O(f_2(n))$, dann $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))$
• R2: $c\cdot f(n)=O(f(n))$ (Konstanten fallen weg)
• R3: Ist $h(n)=O(g(n))$ und $g(n)=O(f(n))$, dann ist $h(n)=O(f(n))$ (Transitivität)
• 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)|$ Für $n>n_3:=\max \{n_1,n_2\}$ gelten beide Ungleichungen gleichzeitig, also $|h(n)|\le c_1|g(n)|\le c_1{c}_2|f(n)|⟹h(n)=O(f(n))\text{ mit }{c}_3:=c_1{c}_2.∎$

Warum $\max \{n_1,n_2\}$?

Jede Aussage gilt erst „ab ihrem“ $n_i$. Beide zusammen gelten erst ab dem späteren der beiden. Der Trick kommt in fast jedem Beweis mit „für fast alle $n$“ vor.

Beispiel zu den Regeln: $g(n)=5n\cdot g_1(n)+(n-1)\cdot g_2(n)\text{mit }{g}_1(n)=O(n),g_2(n)=O(n^2)$ Mit $5n=O(n)$ und $n-1=O(n)$: $g(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)$

Abweichung zur Mitschrift

In der Mitschrift steht im ersten Schritt $5n\cdot O(1)$. Zu $g_1(n)=O(n)$ und zum nächsten Schritt $O(n)\cdot O(n)$ passt aber nur $5n\cdot O(n)$. Mit $O(1)$ käme $O(n)\cdot O(1)=O(n)$ heraus, das Endergebnis $O(n^3)$ bliebe trotzdem gleich.

Achtung: Inklusion, keine Gleichheit

Ist $g(n)=O(n)$, so ist auch $g(n)=O(n^2)$, denn $O(n)\subseteq O(n^2)$. Es gilt aber nicht $O(n^2)=O(n)$, denn $O(n^2)⊈O(n)$: $n^2\ne O(n)$. $O$ ist eine obere Schranke. Eine zu großzügige obere Schranke ist nicht falsch, nur wenig aussagekräftig.

7.7 Typische Laufzeitklassen

$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	☹️

Die Basis des Logarithmus ist egal

${\log }_{a}n=\frac{{\log }_{b}n}{{\log }_{b}a}=\underset{c}{\underbrace{\frac{1}{{\log }_{b}a}}}\cdot {\log }_{b}n$ Logarithmen zu verschiedenen Basen unterscheiden sich nur um einen konstanten Faktor, und Konstanten fallen nach R2 weg. Deshalb schreibt man meist nur $O(\log n)$.

Hierarchie: $O(1)\subset O(\log n)\subset O(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)$ ($O(n)$ fehlt an der Tafel, hier ergänzt. $O(n^k)$ steht für ein festes $k\ge 3$, die Vereinigung über alle $k$ ist „alles Polynomielle“.)

Bezug zu 7.2

Das ist genau die Reihenfolge $T_2<T_3<T_1<T_5<T_4<T_6$ vom 26.10., jetzt als Mengen-Inklusion formuliert.

---

7.8 Weitere Landau-Symbole

Definitionen

Symbol	Definition	Name	Bedeutung
$\Omega (f)$	$\{g:\mathbb{N}\to \mathbb{R}\mid f\in O(g)\}$	Groß-Omega	$g$ wächst mindestens so schnell wie $f$ (untere Schranke)
$\Theta (f)$	$O(f)\cap \Omega (f)$	Groß-Theta	$g$ wächst genau so schnell wie $f$ (bis auf Konstanten)
$o(f)$	$\{g:\mathbb{N}\to \mathbb{R}\mid \lim \frac{g(n)}{f(n)}=0\}$	Klein-o	$g$ wächst echt langsamer als $f$
$\omega (f)$	$\{g:\mathbb{N}\to \mathbb{R}\mid f=o(g)\}$	Klein-Omega	$g$ wächst echt schneller als $f$
$g\sim f$	$\lim \frac{g(n)}{f(n)}=1$	„Schlange“	$g$ und $f$ sind asymptotisch gleich

Bemerkung: Statt $g\in \Omega (f)$, $g\in o(f)$ usw. schreibt man wieder $g=\Omega (f)$, $g=o(f)$ (mit demselben Fallstrick wie bei $O$).

Merkhilfe: Vergleich mit Zahlen

Landau	wie bei Zahlen
$g=O(f)$	$g\le f$
$g=\Omega (f)$	$g\ge f$
$g=\Theta (f)$	$g=f$
$g=o(f)$	$g<f$
$g=\omega (f)$	$g>f$

„Groß“ = mit Gleichheit, „klein“ = echt. Die Analogie ist nicht perfekt (siehe 7.11), hilft aber beim Einordnen.

7.9 Kriterien K3–K5

K3 und K4

• K3: $g(n)=\Omega (f(n))⟺f(n)=O(g(n))$
• K4: $g(n)=\Theta (f(n))⟺g(n)=O(f(n))$ und $f(n)=O(g(n))$

K3 ist einfach die Definition von $\Omega$, K4 die von $\Theta$ als Schnitt.

K5: Das Grenzwert-Kriterium für alles

$\underset{n\to \infty }{\lim }\frac{|g(n)|}{|f(n)|}$	dann gilt
$=0$	$g=o(f)$, $f=\omega (g)$, $g=O(f)$, $f=\Omega (g)$, $g\ne \Theta (f)$
$=a>0$ (endlich)	$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)$

So benutzt man K5

Quotient bilden → Grenzwert ausrechnen (mit den Regeln aus 04 Grenzwert und Konvergenz von Folgen) → Zeile ablesen. Für fast jede Aufgabe „Zeige $g=\Theta (f)$“ ist das der schnellste Weg.

7.10 Beispiel: Polynome

Satz

Ist $p$ ein Polynom vom Grad $k$, d.h. $p(n)=a_k{n}^k+a_{k-1}{n}^{k-1}+\cdots +a_0$ mit $a_k\ne 0$, 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)$.

Beweis: ${\lim }_{n\to \infty }\frac{p(n)}{n^k}={\lim }_{n\to \infty }\left(a_k+\frac{a_{k-1}}{n}+\frac{a_{k-2}}{n^2}+\cdots +\frac{a_0}{n^k}\right)=a_k\ne 0$ $⟹{\lim }_{n\to \infty }\frac{|p(n)|}{n^k}=|a_k|>0\stackrel{K5}{⟹}p(n)=\Theta (n^k)∎$

Praktisch heißt das

Bei Polynomen zählt nur die höchste Potenz. Vorfaktoren und alle kleineren Potenzen fallen weg. Beispiele a) und b) aus 7.5 sind genau dieser Satz für $k=3$.

7.11 Regeln K6, K7

Regeln

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

Begründung: Bei K6 ist der Grenzwert $0\in \mathbb{R}$, also greift K1. Bei K7 ist der Grenzwert $1>0$, also greift die mittlere Zeile von K5.

Denkaufgabe aus der Vorlesung: Wie liegen die Mengen zueinander? (erst selbst überlegen!)

Der Prof hat ein Mengendiagramm gezeichnet (alle Folgen $\mathbb{N}\to \mathbb{R}$, darin $O(f)$, $\Omega (f)$, $\Theta (f)$, $o(f)$, $\omega (f)$, siehe Mitschrift S. 4) und gefragt, ob in den Lücken „noch was liegt“.

Was man sicher weiß:

• $o(f)\subseteq O(f)$ (K6) und $\omega (f)\subseteq \Omega (f)$ (analog)
• $\Theta (f)=O(f)\cap \Omega (f)$ ist die Schnittmenge
• $o(f)\cap \Theta (f)=\varnothing$ und $\omega (f)\cap \Theta (f)=\varnothing$

Die Fragen dazu:

1. Gibt es ein $g\in O(f)$, das weder in $o(f)$ noch in $\Theta (f)$ liegt?

2. Gibt es ein $g$, das weder in $O(f)$ noch in $\Omega (f)$ liegt?

Lösung ja. Der Trick ist, dass der Quotient $\frac{g(n)}{f(n)}$ keinen Grenzwert haben muss. Dann greift K5 nicht. Mit $f(n)=n$:

Beide Male

1. $g(n)=\{\begin{array}{ll}n& n\text{ gerade}\\ 1& n\text{ ungerade}\end{array}$: Es gilt $g\le f$, also $g=O(n)$. Aber $g\ne \Omega (n)$ (die ungeraden Glieder bleiben bei 1), also nicht $\Theta$. Und nicht $o(n)$, weil der Quotient auf geraden $n$ immer 1 ist.
2. $g(n)=\{\begin{array}{ll}{n}^2& n\text{ gerade}\\ 1& n\text{ ungerade}\end{array}$: Auf den geraden $n$ ist $g$ nicht durch $c\cdot n$ beschränkt (also $\ne O(n)$), auf den ungeraden $n$ ist $n$ nicht durch $c\cdot g$ beschränkt (also $\ne \Omega (n)$).

Deshalb hinkt die Merkhilfe „wie bei Zahlen“: Zwei Zahlen sind immer vergleichbar, zwei Folgen nicht.

---

7.12 Stirlingsche Formel

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

a) sagt: Der Quotient aus $n!$ und $\sqrt{2\pi n}(n/e{)}^n$ geht gegen 1, also sind beide asymptotisch gleich. b) ist die genauere Version und sagt, wie schnell dieser Quotient gegen 1 geht. Hier taucht $O$ innerhalb eines Ausdrucks auf: „$+O(\frac{1}{n^2})$“ heißt „plus irgendeine Folge, die höchstens so groß wie $c\cdot \frac{1}{n^2}$ ist“.

Ergänzung (nicht aus der Mitschrift)

Damit sieht man auch, warum in der Hierarchie (7.7) $O(a^n)\subset O(n!)\subset O(n^n)$ gilt: $n!$ verhält sich wie $(n/e{)}^n$ (mal $\sqrt{2\pi n}$). Das wächst schneller als jedes feste $a^n$, aber um den Faktor $e^n$ langsamer als $n^n$.

Selbsttest

1. Zeige mit K5: $3n^2+\lg n=\Theta (n^2)$.
2. Ist $2^{n+1}=O(2^n)$? Ist $2^{2n}=O(2^n)$? (Tipp: Quotient bilden.)
3. Warum ist $O({\log }_{2}n)=O({\log }_{10}n)$?