Definitionen
$ \begin{eqnarray} {\cal O}(g(n)) &:= {f(n) | \exists_{c > 0} \exists_{n_0 > 0} \forall_{n \geq n_0}: f(n) < c \cdot g(n) } \ {\cal 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) } \ \end{eqnarray} $ $\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) }$
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} \subsetneq (n^{2.2}) {\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$
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$
Nummber 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$