Landau-Symbole beschreiben das Wachstum von Funktionen durch Schranken.
Definitionen
\begin{align*}
{\cal O}(g(n)) &:= \{f(n) | \exists_{c > 0} \exists_{n_0 > 0} \forall_{n \geq n_0}: f(n) < c \cdot g(n) \} \\
o(g(n)) &:= \{f(n) | \forall_{c > 0} \exists_{n_0 > 0} \forall_{n \geq n_0}: f(n) < c \cdot g(n) \} \\
\Omega (g(n)) &:= \{f(n) | \exists_{c > 0} \exists_{n_0 > 0} \forall_{n \geq n_0}: f(n) > c \cdot g(n) \} \\
\omega (g(n)) &:= \{f(n) | \forall_{c > 0} \exists_{n_0 > 0} \forall_{n \geq n_0}: f(n) > c \cdot g(n) \} \\
\Theta (g(n)) &:= \{f(n) | \exists_{c_0 > 0} \exists_{c_1 > 0} \exists_{n_0 > 0} \forall_{n > n_0}: c_0 \cdot g(n) < f(n) < c_1 \cdot g(n) \}
\end{align*}
Wichtige Aussagen der Mengen
\begin{align}
f(n) \in {\cal O}(g(n)) &\Leftrightarrow g(n) \in \Omega(f(n)) \\
f(n) \in {\cal o}(g(n)) &\Leftrightarrow g(n) \in \omega(f(n)) \\
f(n) \in {\cal O}(g(n)) \land f(n) \in \Omega(g(n)) &\Leftrightarrow f(n) \in \Theta(g(n)) \\
f(n) \in o(g(n)) &\Leftrightarrow \lim \frac{f(n)}{g(n)} = 0 \\
f(n) \in \Theta ( g(n)) &\Leftrightarrow g(n) \in \Theta(f(n)) \\
f(n) \in \omega(g(n)) &\Leftrightarrow \lim \frac{g(n)}{f(n)} = 0
\end{align}
Logarithmusgesetze
\begin{align}
\log(x \cdot y) &= \log(x) + \log(y) \\
\log(\frac{x}{y}) &= \log(x) – \log(y) \\
\log(x^r) &= r \cdot \log(x)
\end{align}
Wichtige Beziehungen von Funktionen
\({\cal O}(1) \subsetneq {\cal O}(\log n) \subsetneq {\cal O}(n) \subsetneq {\cal O}(n^{2.1}) \subsetneq {\cal O}(n^{2.2}) \subsetneq {\cal O}(n^{100}) \subsetneq {\cal O}(n!) \subsetneq {\cal O}(2^n)\)
\({\cal O}(2^n) \subsetneq {\cal O}(2^{2n}) \subsetneq {\cal O}(3^n) \subsetneq {\cal O}(n^n) \subsetneq {\cal O}(n^{(n^2)}) \subsetneq\)
Wachstum typischer Laufzeiten. Für kleine n liegen die Kurven nah beieinander; ab n = 4 wächst 2ⁿ schneller als n².
Beispiele
Im Folgenden gelte immer:
\(f: \mathbb{N} \rightarrow \mathbb{R^+}\) und \(g:\mathbb{N} \rightarrow \mathbb{R^+}\)
Nummer 1
Voraussetzungen:
Sei \(f(n) := \sqrt{2}^{\lg(n)}\) und \(g(n) := n \cdot \lg(n)\).
Behauptung: \(f \in {\cal O}(g(n))\)
Beweis:
\(f(n) = \sqrt{2}^{\lg(n)} = 10^{\lg(\sqrt{2}^{\lg(n)})} = 10^{\lg(\sqrt{2}) \cdot \lg(n)} = n^{\lg(\sqrt{2})}= n^{\frac{1}{2} \cdot \lg(2)} < n^1 = n\)
Es gilt: \(n \in {\cal O}(n \cdot \lg(n)) = {\cal O}(g(n))\)
\(\Rightarrow f(n) \in {\cal O}(g(n)) \blacksquare\)
Nummer 2
Voraussetzungen:
Sei \(f(n) := \sqrt{5}^{\log_3(n)}\) und \(g(n) := n^2\).
Behauptung: \(f \in {\cal o}(g(n))\)
Beweis:
\(f(n) = \sqrt{5}^{\log_3(n)} = 3^{\log_3(\sqrt{5}^{\log_3(n)})} = 3^{\log_3(5) \cdot \log_3(n)} = n^{\log_3(5)} < n^{\log_3(9)} = n^{\log_3(3^2)} = n^2\)
Sei \(\varepsilon > 0\). Dann gilt:
\(n^{2- \varepsilon} \in o(n^2) \Rightarrow f(n) \in o(g(n)) \blacksquare\)