1. Welt
  2. Quests
  3. #1439
Alexander Fufaev

O-Notation (Landau-Symbol)

aus dem Bereich: Quests
Optionen

Deine Aufgabe ist...

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?

O-Notation (Landau-Symbol) - Wachstumsverhalten Speichern | Info
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) \)
Allgemeine 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 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)\).

Weltkarte
Verwalten
Profil
Die Stimme fragt...
Wie erlange ich den Zugang?

Um das Portal von Ak'tazun betreten zu können, musst Du die rote Pille schlucken. Nachdem Du durch das Portal gegangen bist, gelangst Du in die Matrix, wo Du beispielsweise folgendes tun kannst:

  • Inhalte hinzufügen & verwalten
  • Illustrationen ohne Copyrightzeichen herunterladen
  • Einige Inhalte kommentieren
  • Mittels Kommunikator RT2000 chatten
  • Telegram-Gruppe beitreten
Bist Du dabei?
Ja, bin dabei!
Portale in die anderen Welten

Reise zu den sicheren anderen Welten des Internets, um nach dem Wissen zu suchen. Findest Du eine Welt besonders interessant, dann kannst Du in der Universaldenkerwelt ein Portal zu dieser Welt erbauen, um den anderen Besuchern den schnellen Zugang dazu zu gewährleisten.

Portalraum betreten
Kommunikator
ONLINE 8
Gäste online: 8
Denker online: 0
Der Kommunikator RT2000 funktioniert nur innerhalb der Matrix!
Ich will in die Matrix!Mayday! Kontakt aufnehmen.