Landau-Notation widerlegen

26.10.2019, 18:38	jaaaa	Auf diesen Beitrag antworten »
Landau-Notation widerlegen Meine Frage: Hallo, Könnte mir jemand bei meiner Aufgabe helfen? Man muss folgende Aufgaben beweisen oder wiederlegen. Sei 1 < k $\begin{eqnarray} \in \mathbb N \end{eqnarray}$ a) $\begin{eqnarray} 2^{n+k} \in O \left(2^{n} \right) \end{eqnarray}$ b) $\begin{eqnarray} 2^{2n} \in O \left(2^{n} \right) \end{eqnarray}$ Meine Ideen: a) $\begin{eqnarray} \lim_{n \to \infty } \frac{2^{n} }{2^{n+k} } = \lim_{n \to \infty } \frac{2^{n} }{2^{n}2^{k} } = \frac{1}{2^{k} } \end{eqnarray}$ b) $\begin{eqnarray} \lim_{n \to \infty } \frac{2^{n} }{2^{2n} } = \lim_{n \to \infty } \frac{2^{n} }{2^{n}4 } = \frac{1}{4} \end{eqnarray}$ Ich habe in der Übung , dass man so machen kann. Aber was sagt mir das? Ich verstehe nicht. Ich wäre sehr dankbar wenn jemand mir helfen kann. Liebe Grüße, Jany
26.10.2019, 20:04	HAL 9000	Auf diesen Beitrag antworten »
a) ist richtig. Bei b) solltest du die Potenzregeln noch mal korrekt rekapitulieren.
28.10.2019, 08:48	jaaaa	Auf diesen Beitrag antworten »
Hallo, Danke für deine hilfe. b) ups, ja, wäre dann $\begin{eqnarray} \lim_{n \to \infty } \frac{2^{n} }{4^{n} } \end{eqnarray}$ . Das sagt dass das gegen 0 geht. Aber sagt das, dass das zu 2^n gehört? wie kann ich das erklären?
28.10.2019, 09:04	HAL 9000	Auf diesen Beitrag antworten »
Ich weiß nicht, was da bei dir diesmal im Zähler LaTeX-verunfallt ist, jedenfalls bekommt man wegen $\begin{eqnarray} \frac{2^n}{2^{2n}} = 2^{n-2n} = 2^{-n} = \frac{1}{2^n} \end{eqnarray}$ dort Grenzwert Null.
28.10.2019, 22:34	jaaaa	Auf diesen Beitrag antworten »
ja, stimmt, mein Fehler. Dankeschön
28.10.2019, 22:36	Leopold	Auf diesen Beitrag antworten »
Und welche der Aussagen a),b) ist nun bestätigt oder widerlegt?
Anzeige

28.10.2019, 23:25	HAL 9000	Auf diesen Beitrag antworten »
Ich hatte mich auch etwas gewundert: Für den Nachweis $\begin{eqnarray} f(n)\in O(g(n)) \end{eqnarray}$ betrachtet man ja eher $\begin{eqnarray} \lim_{n\to\infty} \left\|\frac{f(n)}{g(n)}\right\| \end{eqnarray}$ bzw. allgemeiner $\begin{eqnarray} \limsup_{n\to\infty} \left\|\frac{f(n)}{g(n)}\right\| \end{eqnarray}$ statt wie oben $\begin{eqnarray} \lim_{n\to\infty} \left\|\frac{g(n)}{f(n)}\right\| \end{eqnarray}$ . Aber man kann auch aus den "umgekehrten" Quotienten die richtigen Schlüsse für die Landausymbole schließen - wenn man es denn überhaupt mal tut, was Leopold zurecht anmahnt.

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »