O-Notation/Landau-Notation

21.04.2018, 22:40	Lena898	Auf diesen Beitrag antworten »
O-Notation/Landau-Notation Meine Frage: Hallo ich soll prüfen ob $\begin{eqnarray} 2(n^{2})^{4} \in O(4^{n}) \end{eqnarray}$ gilt. Hat jemand einen Tipp wie genau ich bei dieser Aufgabe speziell vorgehen kann ? Meine Ideen: Ich war mir nicht ganz sicher wie ich vorgehen soll.
22.04.2018, 10:55	sibelius84	Auf diesen Beitrag antworten »
Hi, wie in der Mathematik üblich: streng und stur nach Definition. Auf wikipedia unter "Landau-Notation" finde ich das gewöhnliche lateinische große O nicht, vermute aber, dass es das selbe bedeutet wie das geschwungene $\begin{eqnarray} \mathcal O \end{eqnarray}$ . Hier lautet die Definition: $\begin{eqnarray} f\in \mathcal O(g) \quad \Leftrightarrow \quad \limsup_{x\to a}\left\lvert\frac{f(x)}{g(x)}\right\rvert < \infty \end{eqnarray}$ . Wenn du verifizieren kannst, das für das große lateinische O in eurer VL die selbe Definition benutzt wird, dann kannst du mit dieser Definition arbeiten. Zu zeigen oder widerlegen hättest du dann also (da kein Grenzwert genannt ist und die Variable n heißt, gehe ich mal von $\begin{eqnarray} n\to\infty \end{eqnarray}$ aus): $\begin{eqnarray} \limsup_{n\to\infty}\left\lvert\frac{2n^8}{4^n}\right\rvert < \infty \end{eqnarray}$ . Wenn der Limes existiert (was er in solchen Fällen häufig tut), kannst du zunächst vom limsup zum lim übergehen. Zur konkreten Berechnung des Grenzwerts kannst du die Regel von del'Hospital nutzen (8-mal ableiten!), oder mit vollständiger Induktion eine Aussage über den Vergleich der Wachstumsgeschwindigkeiten von Potenz- und Exponentialfolgen beweisen, oder schauen, ob eine solche Aussage in der VL oder auf einem vorherigen ÜB schon mal dran war, so dass du sie ohne Beweis einfach benutzen darfst. LG sibelius84

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »