Übungsaufgaben und Lösungshinweise
Aus ProgrammingWiki
Inhaltsverzeichnis |
Asymptotische Aufwandsordnungen
1. Die Funktionen sind von oben nach unten aufsteigend sortiert.
a)
\begin{align*} f_1(n) &= n^{0.999999} \log n \\ f_2(n) &= 10000000n \\ f_4(n) &= n^2 \\ f_3(n) &= 1.000001^n \\ \end{align*}b)
\begin{align*} f_1(n) &= 2^{2^{1000000}} \\ f_4(n) &= n \sqrt{n} \\ f_3(n) &= \binom{n}{2} \\ f_2(n) &= 2^{1000000n} \\ \end{align*}c)
\begin{align*} f_4(n) &= \sum_{i=1}^n (i + 1) \\ f_1(n) &= n^{\sqrt{n}} \\ f_3(n) &= n^{10} \cdot 2^{\frac{n}{2}} \\ f_2(n) &= 2^n \\ \end{align*}2.
a)
\mathcal{O}(n)b)
\mathcal{O}(n^2)c)
\mathcal{O}(n \cdot m)d)
\mathcal{O}(n)e)
\mathcal{O}(n)f)
\mathcal{O}(n)g)
\mathcal{O}(\log n)h)
\mathcal{O}(\log n)3.
a)
\begin{align} \\ \text{Behauptung: } & \max(f(n), g(n)) \in \Theta(f(n) + g(n)) \\ \\ \text{Fallunterscheidung: } & \\ \\ \max(f(n), g(n)) = f(n) : \\ \\ g(n) < f(n) & \implies f(n) + g(n) < 2 \cdot f(n) \\ \implies f(n) > \frac{1}{2} (f(n) + g(n)) & \implies f(n) \in \Omega(f(n) + g(n)) \\ \implies \max(f(n), g(n)) & \in \Omega(f(n) + g(n)) \\ \\ f(n) \leqslant f(n) + g(n) \text{, mit $g(n) \geqslant 0$ } & \implies f(n) \in \mathcal{O}(f(n) + g(n)) \\ \implies \max(f(n), g(n)) & \in \mathcal{O}(f(n) + g(n)) \\ \\ \max(f(n), g(n)) = g(n) : \\ \\ g(n) < f(n) & \implies f(n) + g(n) < 2 \cdot g(n) & \\ \implies g(n) > \frac{1}{2} (f(n) + g(n)) & \implies g(n) \in \Omega(f(n) + g(n)) \\ \implies \max(f(n), g(n)) & \in \Omega(f(n) + g(n)) \\ \\ g(n) \leqslant g(n) + f(n) \text{ mit $f(n) \geqslant 0$ } & \implies g(n) \in \mathcal{O}(f(n) + g(n)) \\ \implies \max(f(n), g(n)) & \in \mathcal{O}(f(n) + g(n)) \\ \\ \max(f(n), g(n)) \in \mathcal{O}(f(n) + g(n)) \land \max(f(n), g(n)) & \in \Omega(f(n) + g(n)) \implies \max(f(n), g(n)) \in \Theta(f(n) + g(n)) \end{align}b)
\text{Behauptung: } \frac{1}{\Omega(n)} \in \mathcal{O} \left( \frac{1}{n} \right) \frac{1}{\Omega(n)} < \frac{1}{c''1 \cdot n} \text{, mit $\Omega(n) > 1$ } = \frac{1}{c''1} \cdot \frac{1}{n} = c_2 \cdot \frac{1}{n} \text{, mit $c_2 = \frac{1}{c_1}$ } \in \mathcal{O} \left( \frac{1}{n} \right)4.
a)
b)
\mathcal{O}(n^2)5.
Diese Tabelle muss jeder Informatikstudierende einmal in seinem Leben aufgestellt und ausgefüllt haben!