Direkt zum Inhalt
  1. Startseite
  2. Quests
  3. #367

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?

Verschiedenes Wachstumsverhalten

  1. \( 42n + 8 ~\stackrel{?}{\in}~ \mathcal{O}(n) \)
  2. \( 3^n ~\stackrel{?}{\in}~ 2^{\mathcal{O}(n)} \)
  3. \( 5n^3 ~\stackrel{?}{\in}~ 2^{\mathcal{O}(n)} \)
  4. \( n \, \log_2 (n) ~~\stackrel{?}{\in}~ \mathcal{O}(n^2) \)
  5. \( n^4 ~\stackrel{?}{\in}~ \mathcal{O}(n^3 \, \log_2 (n)) \)
  6. \( 6\,n^4 + 7n^3 + 18 ~\stackrel{?}{\in}~ \mathcal{O}(n^5) \)
  7. \(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)\).

Details zum Inhalt
  • Die Quest wurde hinzugefügt von FufaeV am .
  • Die Quest wurde aktualisiert von FufaeV am .

Feedback geben

Hey! Ich bin Alexander FufaeV, der Physiker und Autor hier. Es ist mir wichtig, dass du stets sehr zufrieden bist, wenn du hierher kommst, um deine Fragen und Probleme zu klären. Da ich aber keine Glaskugel besitze, bin ich auf dein Feedback angewiesen. So kann ich Fehler beseitigen und diesen Inhalt verbessern, damit auch andere Besucher von deinem Feedback profitieren können.

Wie zufrieden bist Du?