f(n) = O(n^m)

22.11.2017, 22:48	jni97	Auf diesen Beitrag antworten »
f(n) = O(n^m) Meine Frage: Hallo, ich habe Probleme damit die Aufgabe(im Bildanhang) zu lösen. Meine Ideen: Ich habe mir überlegt, dass $\begin{eqnarray} n^{m} \end{eqnarray}$ genau der Anzahl der Potenzierungen in f(n) entspricht. Aber in wie fern modifiziert das Landau Symbol "O" meine Vermutung und wie beweise ich die Vermutung?
22.11.2017, 22:52	sibelius84	Auf diesen Beitrag antworten »
Hallo jni97, das Landau-Symbol "groß-O" hat eine Definition, die ich mal für dich herausgesucht habe. Da steht genau drin, was du zeigen musst, um deine Behauptung zu beweisen. Versuch mal deine Vorgaben konkret einzusetzen und das durchzurechnen, vielleicht siehst du dann schon mehr. LG sibelius84
22.11.2017, 23:01	jni97	Auf diesen Beitrag antworten »
Ist f (Element von) O(g) die Definition, die gesucht ist? Da steht ja nirgendwo eine Definition für f = O(n^m) Dann würde ich sagen, dass g = n^m ist?
22.11.2017, 23:04	sibelius84	Auf diesen Beitrag antworten »
Genau!
22.11.2017, 23:15	jni97	Auf diesen Beitrag antworten »
Danke erstmal soweit für deine Hilfe! Ich verstehe nur noch nicht so ganz was zu zeigen ist... Muss ich jetzt also beweisen, dass \|f(n) / g(n)\| < ∞ ?
22.11.2017, 23:17	jni97	Auf diesen Beitrag antworten »
Das letze Zeichen sollte natürlich ein $\begin{eqnarray} \infty \end{eqnarray}$
Anzeige

22.11.2017, 23:30	sibelius84	Auf diesen Beitrag antworten »
Wenn du den "lim sup" davorsetzt, ja.
22.11.2017, 23:45	jni97	Auf diesen Beitrag antworten »
Tut mir leid, dass ich so ne blöde Frage stellen muss, aber ich bin noch ein totaler Anfänger in dem Gebiet. Wie soll ich denn das allgemein Beweisen? Ich verstehe nicht so wirklich was ich wo einsetzen muss... Ich kann ja nicht einfach die Polynomfunktion für f(n) und n^m für g(n) einsetzen, weil das bringt mich ja irgendwie nicht weiter.
22.11.2017, 23:47	sibelius84	Auf diesen Beitrag antworten »
Doch! Du musst $\begin{eqnarray} \limsup_{n\to\infty}\left\lvert\frac{f(n)}{g(n)}\right\rvert \end{eqnarray}$ betrachten, wobei f, g genau wie von dir angegeben definiert sind. Zur Grenzwertberechnung in Zähler und Nenner das ausklammern (und anschließend kürzen), was am schnellsten wächst.
22.11.2017, 23:55	jni97	Auf diesen Beitrag antworten »
Aber was schreibe ich für f(n)? Die Funktion ist ja für jedes n und m komplett anders. Ich verstehe nicht was man da dann ausklammern kann, wenn man keinen Wert für n und m hat.
23.11.2017, 00:58	sibelius84	Auf diesen Beitrag antworten »
Machen wir mal ein kleines Beispiel: $\begin{eqnarray} f(n):=0,8n^2+15n+4711 \end{eqnarray}$ , $\begin{eqnarray} g(n):=n^2 \end{eqnarray}$ . Dann haben wir $\begin{eqnarray} \limsup_{n\to\infty}\left\lvert\frac{f(n)}{g(n)}\right\rvert = \limsup_{n\to\infty}\left\lvert\frac{0,8n^2+15n+4711}{n^2}\right\rvert = \limsup_{n\to\infty}\left\lvert\frac{n^2(0,8+\frac{15}{n}+\frac{4711}{n^2})}{n^2}\right\rvert = \limsup_{n\to\infty}\left\lvert\frac{0,8+\frac{15}{n}+\frac{4711}{n^2}}{1}\right\rvert = \lim_{n\to\infty}\left\lvert\frac{0,8+\frac{15}{n}+\frac{4711}{n^2}}{1}\right\rvert = 0,8 \end{eqnarray}$ , weil die beiden Folgen im Zähler mit n bzw. n^2 im Nenner Nullfolgen sind. Du musst dann statt n^2 eben direkt n^m ausklammern.

1

Verwandte Themen