Aufwandsabschätzung: Induktionsbeweis und O-Notation

[mirage228]

Hallo,

In meiner Vorlesung an der Uni nehmen wir für die Aufwandsabschätzung die O-Notation und damit Induktionsbeweis zur Hilfe.

Nun haben wir in einer Übung eine Aufgabe einen Induktionsbeweis für eine O-Notations-Formel zu führen, bei der ich nicht so recht weiterkommen.

Man soll zeigen, dass die Funktion
f(n) = 1/1000 * n^4 + 1000 * n^2 * log(n) Element aus ("E")
O(n^4) ist

Induktionsvorraussetzung ist also:
1/1000 * n^4 + 1000 * n^2 * log(n) < n^4

Beim Induktionsbeweis wähle ich nun eine Konstante c0 vor n^4, welche in diesem Fall auf "1" setze, sowieso ein beliebiges n0, der dann den Induktionsbeginn darstellt (n0 = 1)

Daraus erhält man schonmal (für n = 1):
1/1000 <= 1

Für den Induktionsbeweis macht man nun das ganze für (n + 1):

1/1000 * (n + 1)^4 + 1000 * (n + 1)^2 * log(n + 1) <= (n + 1)^4

Nun an dieser Stelle komme ich nicht weiter. Es gilt ja z.B. oben c0 möglichst geschickt zu wählen um hier u.A. auch mittels der Induktionsvorraussetzung beweisen zu können, dass diese Ungleichung zutrifft.

Wir hatten in der Vorlesung ein Beispiel in der auf der rechten Seite (also bei (n + 1)^4) die Induktionssvorraussetzung verwendet worden ist, damit kam ich allerdings nicht weiter.

Weiß wer von euch Rat oder kann mir evtl. bei dem Ansatz helfen?

Im Anhang noch mal die Aufgabenstellung mit den Originalsymbolen als GIF-Screenshoft aus dem PDF.

Viele Grüße

[3_of_8]

Da steht jetzt nur "Zeigen Sie", nicht "Zeigen Sie durch vollständige Induktion". Musst du das wirklich mit Induktion machen, also steht das explizit in der Aufgabe drin bzw. wurde es dir so gesagt? Ansonsten würde ich das einfach durch Grenzwertrechnung beweisen.

[Dani]

Ich würde nicht zeigen, dass gilt:

1/1000 * (n + 1)^4 + 1000 * (n + 1)^2 * log(n + 1) <= (n + 1)^4

sondern:

1/1000 * (n + 1)^4 + 1000 * (n + 1)^2 * log(n + 1) ELEMENT O(n^4)

[ninja-edit]

[Gausi]

Du musst ja nur ein n0 und ein c wählen - nimm doch einfach n0=10.000 und c=2.

Dann gilt:

Code:

  1/1000 * 10.000^4   +   1000 * 10.000^2 * log(10.000)
< 1/1000 * 10.000^4  + 10.000^4
< 2* 10.000^4

Und für n>10.000 gilt das auch.

[mirage228]

Zitat:

Zitat von 3_of_8

Da steht jetzt nur "Zeigen Sie", nicht "Zeigen Sie durch vollständige Induktion". Musst du das wirklich mit Induktion machen, also steht das explizit in der Aufgabe drin bzw. wurde es dir so gesagt? Ansonsten würde ich das einfach durch Grenzwertrechnung beweisen.

Ah ja, sorry, wir hatten es in der Vorlesung so gemacht (halt mit simpleren Beispielen) und ich denke daher, dass wir das schon so machen sollen.

Zitat:

Zitat von Dani

Im Induktionsschritt musst du nicht zeigen, dass gilt:

1/1000 * (n + 1)^4 + 1000 * (n + 1)^2 * log(n + 1) <= (n + 1)^4

sondern:

1/1000 * (n + 1)^4 + 1000 * (n + 1)^2 * log(n + 1) ELEMENT O(n^4)

reicht das schon?

Wir hatten auf jeden Fall in den Beispielen eine Termumformung durchgeführt. Ich hatte dabei eher die Vermutung, dass da gewisse Eigenheiten der Terme ausgenutzt wurden. z.B. ein Umformungsschritt im Beispiel (verkürzt):

IV: 42*n <= 42*n^2 + 1
zu zeigen: 42*(n+1) <= 42*(n+1)^2 + 1

42*(n+1) = 42n + 42
42n + 42 <= (IV) 42*n^2 + 1 + 42 <= 42*n^2 + 84*n + 42 +1 = 42*(n+1)^2 + 1

Edit: Äh, das sieht so vielleicht doch etwas kompliziert aus, habs doch mal eingescannt und angehangen ;-)
Ist zwar in dem Beispiel nicht mit c0 und n0 sondern mit zwei "c"s, aber die beiden Methoden sind letzlich equivalent...

Also da wird die eine Seite auf die andere umgeformt, ich frage mich nur wie der Ansatz ist und wie man da am besten vorgeht...

Zitat:

Zitat von Gausi

Du musst ja nur ein n0 und ein c wählen - nimm doch einfach n0=10.000 und c=2.

Dann gilt:

Code:

  1/1000 * 10.000^4   +   1000 * 10.000^2 * log(10.000)
< 1/1000 * 10.000^4  + 10.000^4
&lt; 2* 10.000^4

Und für n>10.000 gilt das auch.

Und das reicht auch für eine vollständige Induktion? Also wir hatten ja ein n gewählt (ich ja oben auch) und dann sollte das halt nochmal für n -> n + 1 bewiesen werden... (in dem "Stil" wie in dem verkürzten Beispiel von mir genannt)

Danke für eure Antworten!

Viele Grüße