Aufwandsabschätzung: Induktionsbeweis und O-Notation

[mirage228]

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 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 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