Level 3
Aufgabe mit Lösung O-Notation (Landau-Symbol)
Hier muss das asymptotische Wachstumsverhalten verschiedener Funktionen untersucht werden, die beispielsweise die Laufzeit eines Algorithmus beschreiben könnten. Welche der folgenden Aussagen ist wahr und welche falsch?
- \( 42n + 8 ~\stackrel{?}{\in}~ \mathcal{O}(n) \)
- \( 3^n ~\stackrel{?}{\in}~ 2^{\mathcal{O}(n)} \)
- \( 5n^3 ~\stackrel{?}{\in}~ 2^{\mathcal{O}(n)} \)
- \( n \, \log_2 (n) ~~\stackrel{?}{\in}~ \mathcal{O}(n^2) \)
- \( n^4 ~\stackrel{?}{\in}~ \mathcal{O}(n^3 \, \log_2 (n)) \)
- \( 6\,n^4 + 7n^3 + 18 ~\stackrel{?}{\in}~ \mathcal{O}(n^5) \)
- \(n \, \log_2(n) + n^2 \, \sqrt{n} ~\stackrel{?}{\in}~ \mathcal{O}(n^4) \)
Lösungstipps
Benutze die Definition des O-Symbols:\[ \mathcal{O}(f) ~=~ \{~g ~|~ \exists \, c_1, c_2 > 0, \forall n \in \mathbb{N}: g(n) \leq c_1 \, f(n) + c_2~\} \]und betrachte die jeweiligen Ungleichungen:\[ g(n) ~\leq~ c_1 \, f(n) + c_2 \]
Lösung
Lösung zu (a) anzeigen
Die Aussage \( 42n + 8 ~\in~ \mathcal{O}(n) \) ist wahr, denn mit \( g(n) = 42n \) und \(f(n) = n \) folgt nach der Definition des O-Symbols (siehe Hinweis):1\[ 42n + 8 ~\leq~ c_1 \, n + c_2 \]mit \(c_1 ~\geq~ 42, c_2 ~\geq~ 8\).
Lösung zu (b) anzeigen
Mit \( g(n) = 3^n \) und \(f(n) = n \) folgt nach der Definition des O-Symbols:2\[ 3^n ~\stackrel{?}{\leq}~ 2^{c_1 \, n + c_2} \]3\[ e^{\ln(3)\,n} ~\stackrel{?}{\leq}~ e^{\ln(2)\, (c_1 \, n + c_2)} \]4\[ \ln(3)\,n ~\leq~ \ln(2)\, (c_1 \, n + c_2) \]
Für \(c_1 ~\geq~ \ln(3) / \ln(2) \) ist 2
erfüllt und damit \( 3^n \in 2^{\mathcal{O}(n)} \) wahr.
Lösung zu (c) anzeigen
Mit \( g(n) = 5n^3 \) und \(f(n) = n \) folgt nach der Definition des O-Symbols:5\[ 5n^3 ~\stackrel{?}{\leq}~ 2^{c_1 \, n + c_2} \]6\[ 5n^3 ~\stackrel{?}{\leq}~ e^{\ln(2)\, (c_1 \, n + c_2)} \]
Vergleich der dritten Ableitungen (Regel von de l’Hospital) von 6
:7\[ 30 ~\leq~ e^{\ln(2)\, (c_1 \, n + c_2)} \, (\ln(2)\, c_1)^3 \]
Da 7
erfüllt ist, ist \( 5n^3 \in 2^{\mathcal{O}(n)} \) wahr.
Lösung zu (d) anzeigen
Mit \( g(n) = n\,\log_2(n) \) und \(f(n) = n^2 \) folgt nach der Definition des O-Symbols:8\[ n\,\log_2(n) ~\stackrel{?}{\leq}~ c_1 \, n^2 + c_2 \]
Teile auf beiden Seiten durch \(n\):9\[ \log_2(n) ~\stackrel{?}{\leq}~ c_1 \, n + \frac{c_2}{n} \]
Gleichung 9
ist erfüllt, falls folgende Gleichung erfüllt ist (denn \(\frac{c_2}{n} \geq 0 \)):10\[ \log_2(n) ~\stackrel{?}{\leq}~ c_1 \, n \]11\[ n ~\stackrel{?}{\leq}~ 2^{c_1 \, n} \]
Da 11
erfüllt ist, ist \( n\,\log_2(n) \in \mathcal{O}(n^2) \) wahr.
Lösung zu (e) anzeigen
Mit \( g(n) = n^4 \) und \(f(n) = n^3\,\log_2(n) \) folgt nach der Definition des O-Symbols:12\[ n^4 ~\stackrel{?}{\leq}~ c_1 \, n^3\,\log_2(n) + c_2 \]
Teile 12
auf beiden Seiten durch \(n^4\):13\[ 1 ~\stackrel{?}{\leq}~ c_1 \, \frac{1}{n}\,\log_2(n) + \frac{c_2}{n^4} \]
Für große \(n\) geht \(c_2/n^4\) gegen Null und kann bei großen \(n\) vernachlässigt werden:14\[ 1 ~\stackrel{?}{\leq}~ c_1 \, \frac{1}{n}\,\log_2(n) \]
Rechne auf beiden Seiten \(2^x\):15\[ 2 ~\stackrel{?}{\leq}~ 2^{\frac{c_1 \, \log_2(n)}{n}} \]16\[ 2 ~\stackrel{?}{\leq}~ \left(2^{\log_2(n)}\right)^{\frac{c_1}{n}} \]17\[ 2 ~\not\leq~ n^{\frac{c_1}{n}} \]
Ungleichung 17
ist für große \(n\) nicht erfüllt, denn der Exponent auf der rechten Seite geht gegen 0. Damit ist der Grenzwert auf der rechten Seite \(n^0 = 1 \). Es gibt also keine Konstante \(c_1\), sodass ab einem festen \(n\) die Ungleichung immer erfüllt wäre. Folglich ist \( n^4 \not\in \mathcal{O}(n^3\,\log_2(n)) \) wahr.
Lösung zu (f) anzeigen
Mit \( g(n) = 6\,n^4 + 7n^3 + 18 \) und \(f(n) = n^5 \) folgt nach der Definition des \(\mathcal{O}\)-Symbols:18\[ 6\,n^4 + 7n^3 + 18 ~\stackrel{?}{\leq}~ c_1 \,n^5 + c_2 \]
Teile auf beiden Seiten durch \(n^4\)19\[ 6 + \frac{7}{n} + \frac{18}{n^4} ~\leq~ c_1 \,n + \frac{c_2}{n^4} \]
Jeder Summand, in dem \(n\) im Nenner steht, geht im Gegensatz zum linearen Term \( c_1 \,n \) gegen Null. Folglich existieren Konstanten \(c_1, c_2\) für die die Ungleichung 19
erfüllt ist. Damit ist \(6\,n^4 + 7n^3 + 18 \in \mathcal{O}(n^5)\).
Lösung zu (g) anzeigen
Mit \( g(n) = n \, \log_2(n) + n^2 \, \sqrt{n} \) und \(f(n) = n^4 \) folgt nach der Definition des \(\mathcal{O}\)-Symbols:20\[ n \, \log_2(n) + n^2 \, \sqrt{n} ~\stackrel{?}{\leq}~ c_1 \, n^4 + c_2 \]
Teile auf beiden Seiten durch \(n\):21\[ \log_2(n) + n \, \sqrt{n} ~\stackrel{?}{\leq}~ c_1 \, n^3 + \frac{c_2}{n} \]
Ungleichung 21
ist erfüllt, falls folgende Ungleichung erfüllt ist (da \(\frac{c_2}{n} \geq 1 \)):22\[ \log_2(n) + n \, \sqrt{n} ~\stackrel{?}{\leq}~ c_1 \, n^3 \]23\[ \log_2(n) ~\stackrel{?}{\leq}~ c_1 \, n^3 - n \, \sqrt{n} \]
Wende auf beiden Seiten \(2^x\) an:24\[ n ~\stackrel{?}{\leq}~ 2^{ c_1 \, n^3 - n \, \sqrt{n} } = 2^{ n \, (c_1 \, n^2 - \sqrt{n})} \]
Ungleichung 24
ist erfüllt, falls folgende Ungleichung erfüllt ist (da \(c_1 \, n^3 - n \, \sqrt{n} \geq 0 \)):25\[ n \leq 2^n \]
25
ist erfüllt, deshalb ist \(n \, \log_2(n) + n^2 \, \sqrt{n}\) in der Menge \(\mathcal{O}(n^4)\).