Asymptotische Notation¶
Begriffsklärung: Analyse von Algorithmen¶
Die Analyse von Algorithmen entspricht dem theoretischem Studium eines Computerprogramms in Hinblick auf Performanz und Resourcenverbrauch (Kommunikationsaufwand, Speicherverbrauch).
Laufzeitanalyse (Performanz)¶
- Wie verhält sich die Laufzeit des Algorithmus in Abhängigkeit von der Größe der Eingabedaten.
- Insbesondere interessant, wie die Abhängigkeit für große Daten aussieht.
- Asymptotisches Verhalten für $n \rightarrow \infty$ mit $n$ Größe/Anzahl der Eingabedaten.
Asymptotische Notation¶
- Terme "niedriger Ordnung" werden ignoriert.
- Diese spielen asymptotisch keine Rolle, da Terme "größerer Ordnung" diese unterdrücken.
- Konstanten spielen keine Rolle.
- da Konstanten systemabhängig (Programmiersprache, Maschine etc.) sind.
Beispiel MergeSort:
statt $6 n \log_2 n+ 6 n$ sagt man die Laufzeit von $n$ ist "$n \log n$"
Weitere Beispiele¶
Searching One Array¶
Input: array $A$ of $n$ intergers, and an integer $t$
Output: Whether or not $A$ contains $t$
for $i := 1$ to $n$ do
if $A[i] = t$ then
returnTRUE
returnFALSE
Wie ist die asymptotische Laufzeit in Abhängigkeit von $n$?
Searching Two Arrays¶
Input: arrays $A$ and $B$ of $n$ intergers each, and an integer $t$
Output: Whether or not $A$ or $B$ contains $t$
for $i := 1$ to $n$ do
if $A[i] = t$ then
returnTRUE
for $i := 1$ to $n$ do
if $B[i] = t$ then
returnTRUE
returnFALSE
Wie ist die asymptotische Laufzeit?
Checking for a Common Element¶
Input: arrays $A$ and $B$ of $n$ intergers each
Output: Whether or not there is an integer $t$ contained in both $A$ and $B$
for $i := 1$ to $n$ do
for $j := 1$ to $n$ do
if $A[i] = B[j]$ then
returnTRUE
returnFALSE
Wie ist die asymptotische Laufzeit?
Checking for Duplicates¶
Input: arrays $A$ of $n$ intergers each
Output: Whether or not $A$ contains an integer more then once.
for $i := 1$ to $n$ do
for $j := i+1$ to $n$ do
if $A[i] = A[j]$ then
returnTRUE
returnFALSE
Wie ist die asymptotische Laufzeit?
Big O-Notation¶
- Für Funktionen $T(n)$ definiert auf den natürlichen Zahlen $n \in \{ 1,2, \dots \}$ ($n \in \mathbb N$) sind wir an einer oberen Schranke (upper bound) für die Funktion $T(n)$ interessiert.
- $T(n)$ ist in der Regel die Laufzeit unseres Algorithmus im schlimmsten Fall (worst case).
Big O-Notation: Formale Definition¶
$T(n) \in O\left(f\left(n\right)\right)$ gilt, wenn und nur wenn (if and only if: iff) eine positive Konstante $c$ und ein $n_0$ exisitieren mit
$$T(n) \leq c \cdot f(n)$$für alle $n \geq n_0$.
Beispiel¶
- $f(n) = n$
- $g(n) = n^2$
mit $n_0=1$ und $c=1$:
$\forall n \geq 1: f(n) \leq g(n) \Leftrightarrow f \in O(g)$
aber $g \notin O(f)$
Beispiel¶
- $f(n) = n$
- $g(n) = n/2$
mit $c=2$:
$\forall n: f(n) \leq 2 g(n)$ $\Leftrightarrow$ $f \in O(g)$
und auch $g \in O(f)$
Beispiel¶
plot_O_example()
Für alle $ n \geq n_0\approx 500$ gilt mit $c=2$: $T(n) \leq c \cdot n$
also ist $T(n) \in O(n)$
Beispiel: Polynom vom Grad $k$¶
Proposition 2.1:
$T(n)$ sei ein Polynom vom Grad $k$, d.h. $$ T(n) = a_0 + a_1 n + a_2 n^2 + \dots + a_k n^k $$ mit
- $k \in \mathbb N$ (positive, ganze Zahlen)
- $a_i \in \mathbb R$ (reeele Zahlen)
Dann gilt $T(n) \in O(n^k)$, d.h. nur der Term höchster Ordnung spielt asymptotisch eine Rolle.
Zum Verständnis der Definition der asymptotischen Notation, hier $T(n)\leq c \cdot n^k$ für alle $n\geq n_0$, beweisen wir das:
mit
- $n_0 = 1$
- Die erste Ungleichung gilt, da $n^i$ positiv ist ($n \in \mathbb N$).
- Die zweite Ungleichung gilt für alle $n \geq n_0 =1$
- die Konstante $c$ ist dabei $c = |a_0| + |a_1| + \dots + |a_k|$
QED (quod erat demonstrandum - was zu beweisen war)
Beispiel¶
Mit $T(n) = n^k$ ($k \in \mathbb N$) ist $T(n)$ nicht in $O(n^{k-1})$ (Preposition 2.2)
Beweis durch Widerspruch (contradiction) der (falschen) Annahme $n^k \in O(n^{k-1})$.
Aus der Annahme folgt $n^k \leq c \cdot n^{k-1}$ für alle $n\geq n_0$.
Kürzen ergibt $n\leq c $ wieder für alle $n\geq n_0$.
Dies würde bedeuten, dass $c$ größer ist als jede positive Zahl.
Dies kann aber nicht sein, z.B. kann $c$ nicht größer als $c+1$ gerundet auf die nächste Ganzzahl sein.
D.h. hier gibt es einen Widerspruch. QED
Big Omega- und Big Theta-Notation¶
Big Omega-Notation: Formale Definition¶
$T(n) \in \Omega\left(f\left(n\right)\right)$ gilt, wenn und nur wenn (if and only if: iff) eine positive Konstante $c$ und ein $n_0$ exisitieren mit
$$T(n) \geq c \cdot f(n)$$für alle $n \geq n_0$.
Vergleiche die Big-O Notation mit der Big-Omega Notation: Das Ungleichheitszeichen ist andersherum!
- Big-O definiert eine asymptotische obere Grenze
- Big-Omega definiert eine asymptotische untere Grenze
Big Theta-Notation: Formale Definition¶
$T(n) \in \Theta\left(f\left(n\right)\right)$ gilt, wenn und nur wenn (if and only if: iff) zwei positive Konstanten $c_1$ und $c_2$ und ein $n_0$ exisitieren mit
$$ c_1 \cdot f(n) \leq T(n) \leq c_2 \cdot f(n)$$für alle $n \geq n_0$.
D.h. wenn $T(n) \in \Theta\left(f\left(n\right)\right)$ gilt sowohl $T(n) \in O\left(f\left(n\right)\right)$ als auch $T(n) \in \Omega\left(f\left(n\right)\right)$ und umgekehrt.
Zusammenfassung¶
- Der Zweck der asymptotichen Notation ist es konstante Faktoren (zu systemabhängig) und Terme niedriger Ordnung (werden von Termen höherer Ordnung unterdrückt) zu vernachlässigen.
- Obere Grenze für $T(n)$ und große $n$
- $T(n) \in O\left(f\left(n\right)\right)$ gilt, wenn und nur wenn eine positive Konstante $c$ und ein $n_0$ exisitieren mit $T(n) \leq c \cdot f(n)$ für alle $n \geq n_0$.
- Untere Grenze für $T(n)$ und große $n$
- $T(n) \in \Omega \left(f\left(n\right)\right)$ gilt, wenn und nur wenn eine positive Konstante $c$ und ein $n_0$ exisitieren mit $T(n) \geq c \cdot f(n)$ für alle $n \geq n_0$.
- Big-Theta $\Theta$
- $T(n) \in \Theta \left(f\left(n\right)\right)$ wenn $O\left(f\left(n\right)\right)$ und $\Omega \left(f\left(n\right)\right)$ gilt.