O-Notation / Grenzwertberechnung

Neue Frage »

11.02.2012, 11:35	rawfood	Auf diesen Beitrag antworten »
O-Notation / Grenzwertberechnung Hallo Leute, Ich habe ein Problem mit folgender Aufgabe: gilt $\begin{eqnarray} 3 \cdot \sqrt{n}+25 \in O(n) \end{eqnarray}$ Also fing ich an folgendermaßen an die Sache heranzugehen : $\begin{eqnarray} <br /> \lim_{n \to \infty} \frac{3\sqrt{n}+5}{n}<br /> \end{eqnarray}$ $\begin{eqnarray} <br /> \lim_{n \to \infty}\frac{\sqrt{n}(3+\frac{5}{\sqrt{n}})}{n}<br /> \end{eqnarray}$ $\begin{eqnarray} <br /> \lim_{n \to \infty} \frac{n(3+\frac{5}{\sqrt{n}})^2}{n^2}<br /> \end{eqnarray}$ $\begin{eqnarray} <br /> \lim_{n \to \infty} \frac{(3+\frac{5}{\sqrt{n}})^2}{n}<br /> \end{eqnarray}$ $\begin{eqnarray} <br /> \lim_{n \to \infty} \frac{9+\frac{30}{\sqrt{n}}+\frac{25}{n}}{n}<br /> \end{eqnarray}$ $\begin{eqnarray} <br /> \lim_{n \to \infty} 9n+\frac{30n}{\sqrt{n}}+25<br /> \end{eqnarray}$ $\begin{eqnarray} <br /> \lim_{n \to \infty} 9n+30\sqrt{n}+25<br /> \end{eqnarray}$ Ich finde meinen Ansatz irgendwie völlig mißlungen. Desweiteren habe ich mir mal den Graphen von oberer Funktion angeschaut und gleichzeitig die Funktion von n. Ab n_{0}=17,5 bildet n die obere Schranke. Aber formal wird es mir nicht reichen, wenn ich auf eine Graphische darstellung verweise. Weiß jemand wie man sowas zeigt? Lg Rf
11.02.2012, 11:44	rawfood	Auf diesen Beitrag antworten »
Ich habe es nochmal anders gemacht. $\begin{eqnarray} <br /> \lim_{n \to \infty} \frac{3\sqrt{n}+5}{n}<br /> \end{eqnarray}$ $\begin{eqnarray} <br /> \lim_{n \to \infty} \frac{9n+25}{n^2}<br /> \end{eqnarray}$ $\begin{eqnarray} <br /> \lim_{n \to \infty} \frac{n(9+\frac{25}{n})}{n^2}<br /> \end{eqnarray}$ $\begin{eqnarray} <br /> \lim_{n \to \infty} \frac{9+\frac{25}{n}}{n}<br /> \end{eqnarray}$ $\begin{eqnarray} <br /> \lim_{n \to \infty} 9n+\frac{25}{n}n<br /> \end{eqnarray}$ $\begin{eqnarray} <br /> \lim_{n \to \infty} 9n+25<br /> \end{eqnarray}$ Ich glaube so hab ich es gezeigt :-) was meint ihr? lg rf
11.02.2012, 12:33	Trak92	Auf diesen Beitrag antworten »
Beide male hättest du nur das Gegenteil gezeigt, und auch das mit inkorrekten Rechenschritten. Man darf einen Bruch nicht einfach im Zähler und im Nenner quadrieren. Und beim zweiten versuch hast auch nicht richtig quadriert... Du hast den Ausdruck: $\begin{eqnarray} \lim_{n\rightarrow \infty}\frac{3\sqrt{n}+5}{n} \end{eqnarray}$ Da steht im Nenner eine Zahl und oben eine Summe. Was ist also der direkteste Weg den Ausdruck einfacher zu machen?
11.02.2012, 18:42	rawfood	Auf diesen Beitrag antworten »
Danke Trak. Ich werds mir merken. Das Quadrieren einer rationalen Zahl werde ich unterlassen. $\begin{eqnarray} \lim_{n \to \infty}\frac{ 3\sqrt{n}+5}{n} \end{eqnarray}$ $\begin{eqnarray} \lim_{n \to \infty}3\sqrt{n}n+5n<br /> \end{eqnarray}$ $\begin{eqnarray} <br /> \lim_{n \to \infty}n(3\sqrt{n}+5)<br /> <br /> \end{eqnarray}$ So, ich denke, dass muss ich es so machen! Aber was kann ich daraus nun für Schlüsse ziehen? Die Funktion geht für n gegen unendlich. Eine lineare Steigung ist definiert mit mx+b. Ich habe nun aber gezeigt, dass es mx*bx ist. Die Wurzel vernachlässige ich jetzt mal. Also ist damit gezeigt worden, dass es stärker als linear ansteigt, und nicht in O(n) vorhanden ist. Ist diese Argumentation zulässig? Lg rf
11.02.2012, 18:57	rawfood	Auf diesen Beitrag antworten »
Irgendwie weiß ich total nicht was ich tue!!! Gerade habe ich mir nochmal die Graphen $\begin{eqnarray} g(n) = 3 \sqrt{n}+5 \end{eqnarray}$ angeschaut und f(n)=n. Ab dem Argument 17, steigt f(n) steiler als g(n), von daher ist g(n) nach oben durch c*f(n) begrenzt. Kann mir jemand sagen, wie ich das durch den Limes zeige?
11.02.2012, 21:16	Trak92	Auf diesen Beitrag antworten »
sorry war lange offline Wie teilst du denn bitte? $\begin{eqnarray} \frac{3\sqrt{n}+n}{n}=n(3\sqrt{n}+5) \end{eqnarray}$ Das ist gleichbedeutend mit: $\begin{eqnarray} (3\sqrt{n}+5)\cdot \frac{1}{n}=(3\sqrt{n}+5)\cdot \frac{n}{1}\Leftrightarrow n=1 \end{eqnarray}$ was eben nur für n=1 gilt richtig muss es natürlich sein: $\begin{eqnarray} \frac{3\sqrt{n}+n}{n}=3\frac{n^{1/2}}{n}+\frac{5}{n} \end{eqnarray}$ Davon jetz den Limes, und du solltest dir die Bruchregeln nochmal durchlesen...
Anzeige

12.02.2012, 10:42	rawfood	Auf diesen Beitrag antworten »
Danke, Ich werde mir die Bruchrechengesetze nochmal anschauen müssen. Der Grenzwert konvergiert gegen null. Wenn der Grenzwert gegen Null geht, kann ich dann daraus schließen, dass meine Funktion aus O(n) ist? Welche Wertemenge würde alles implizieren, dass meine Funktion aus O(n) ist?
12.02.2012, 11:12	Trak92	Auf diesen Beitrag antworten »
wenn eine Funktion f(x)=O(g(x)) ist und g(x) nicht die Nullfunktion, dann heisst das das der Limes (korrekterweise Limes superior) von Betrag (f/g) mit x nach unendlich (oder nach a je nachdem worum es in der aufgabe geht) kleiner als unendlich ist... Hier ist der Limes nach unendlich Null deswegen ist f(n)=O(g(n)) füe x nach unendlich.. f(n) ist sogar element von o(n)... Es ist aber wichtig anzugeben, gegen welchen Wert für x der Limes genommen wird, denn gegen verschiedene x-Werte können die Funktionen unterschiedlich schnell steigen.... P.S. In meiner vorigen Antwort hätte n auch -1 sein können, dann wärs aber komlplex...
12.02.2012, 12:21	rawfood	Auf diesen Beitrag antworten »
Vielen Dank Trek92. Ich lese gerade erneut das erste Kapitel des Skripts und bin über die Antwort gestoßen. Dort steht wie du schon in anderen Worten sagtest: Wenn der Grenzwert existiert, so gilt f=O(g). Falls der Grenzwert 0 ist, gilt natürlich auch f=O(g) und g wächst sogar echt schneller als f; Dies wird dann wohl wie du schon gesagt hast mit f=o(g) ausgedrückt. Würde f(n)/g(n) grenzenlos wachsen, dann wäre f nicht in O(g) :-) rf

Neue Frage »

Antworten »

O-Notation / Grenzwertberechnung

Verwandte Themen