Rekursionsbasis? < Folgen und Reihen < eindimensional < reell < Analysis < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 17:28 So 13.01.2013 | | Autor: | bandchef |
| Aufgabe | Bestimmen Sie exakte Schranken für die folgende Rekursionsgleichungen von Algorithmen mit Hilfe der Iterations- oder Substitutionsmethode:
$T(1)=1, T(2) = 1, T(3) =1, T(n) = 2T(n-1) + [mm] n^2 \forall [/mm] n>3$ |
Hi Leute!
Ich hab jetzt im ersten Schritt erstmal versucht das Bildungsgesetz der Rekursionsformel zu "erkennen". Dazu hab ich die Rekursionsformel für die ersten Werte ausgerollt:
$T(n) = [mm] 2T(n-1)+n^2= 2(2T(n-2)+(n-1)^2)+n^2 [/mm] = [mm] 4T(n-2)+2(n-1)^2+n^2 [/mm] =$
[mm] $2(2(2T(n-3)+(n-2)^2)+(n-1)^2)+n^2 [/mm] = [mm] 8T(n-3)+4(n-2)^2+2(n-1)^2+n^2$
[/mm]
Ich komm dann auf diese Formel: $ T(n) = [mm] 2^i\cdot T(n-i)+\sum_{k=0}^{i-1}\left( 2^k(n-k)^2 \right)$
[/mm]
Um hier nun weiter machen zu können, muss ich laut Prof. nun das Argument dieser "neuen Formel" hier direkt drüber mit der Rekursionsbasis gleichsetzen: $n-i = 3 [mm] \Leftrightarrow [/mm] i = n-3$.
So und nun kommt die Frage: WOHER weiß ich ich, dass ich $n-i$ (das quasi "neue" Argument der Rekursionsformel) ausgerechnet mit 3 gleichsetzen muss? Ich vermute, dass es mit den bei der Aufgabenstellung angegebenen Werten zu tun hat. Aber woher weiß ich das ich nicht mit 1 gleichsetzen muss? Es steht ja auch $T(1)=1$ oder mit 2 gleichsetzen, denn es steht ja auch $T(2) = 1$? (1 und 2 waren hier wieder auf die Argumente bezogen!)
Oder gibt mir das [mm] $\forall [/mm] n>3$ Aufschluss darüber was ich mit $n-i$ gleichsetzen muss? Was muss ich aber dann tun, wenn diese Einschränkung mal nicht gegeben ist sonder nur $T(1)=1, T(2) = 1, T(3) =1$?
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 15:59 Mo 14.01.2013 | | Autor: | bandchef |
Hi Leute,
ich will ja nicht drängen, aber kann mir hier wirklich keiner eine Antwort auf meine Frage geben?
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 16:37 Mo 14.01.2013 | | Autor: | meili |
Hallo,
> Bestimmen Sie exakte Schranken für die folgende
> Rekursionsgleichungen von Algorithmen mit Hilfe der
> Iterations- oder Substitutionsmethode:
>
> [mm]T(1)=1, T(2) = 1, T(3) =1, T(n) = 2T(n-1) + n^2 \forall n>3[/mm]
>
> Hi Leute!
>
> Ich hab jetzt im ersten Schritt erstmal versucht das
> Bildungsgesetz der Rekursionsformel zu "erkennen". Dazu hab
> ich die Rekursionsformel für die ersten Werte ausgerollt:
>
> [mm]T(n) = 2T(n-1)+n^2= 2(2T(n-2)+(n-1)^2)+n^2 = 4T(n-2)+2(n-1)^2+n^2 =[/mm]
>
> [mm]2(2(2T(n-3)+(n-2)^2)+(n-1)^2)+n^2 = 8T(n-3)+4(n-2)^2+2(n-1)^2+n^2[/mm]
>
> Ich komm dann auf diese Formel: [mm]T(n) = 2^i\cdot T(n-i)+\sum_{k=0}^{i-1}\left( 2^k(n-k)^2 \right)[/mm]
>
> Um hier nun weiter machen zu können, muss ich laut Prof.
> nun das Argument dieser "neuen Formel" hier direkt drüber
> mit der Rekursionsbasis gleichsetzen: [mm]n-i = 3 \Leftrightarrow i = n-3[/mm].
>
> So und nun kommt die Frage: WOHER weiß ich ich, dass ich
> [mm]n-i[/mm] (das quasi "neue" Argument der Rekursionsformel)
> ausgerechnet mit 3 gleichsetzen muss? Ich vermute, dass es
> mit den bei der Aufgabenstellung angegebenen Werten zu tun
> hat. Aber woher weiß ich das ich nicht mit 1 gleichsetzen
> muss? Es steht ja auch [mm]T(1)=1[/mm] oder mit 2 gleichsetzen, denn
> es steht ja auch [mm]T(2) = 1[/mm]? (1 und 2 waren hier wieder auf
> die Argumente bezogen!)
Die Rekursion $T(n) = 2T(n-1) + [mm] n^2$ [/mm] gilt ja nur für n > 3.
T(2) und T(3) lassen sich so nicht berechnen.
Also ist das kleinste n-1, das mit T(n-1) in der Rekursion vorkommt 3.
Und dieses T(3) wird auch in [mm]T(n) = 2^i\cdot T(n-i)+\sum_{k=0}^{i-1}\left( 2^k(n-k)^2 \right)[/mm] für T(n-i) gebraucht,
weil dieses T(n-i) das erste der gesamten Rekursion ist.
>
> Oder gibt mir das [mm]\forall n>3[/mm] Aufschluss darüber was ich
> mit [mm]n-i[/mm] gleichsetzen muss? Was muss ich aber dann tun, wenn
> diese Einschränkung mal nicht gegeben ist sonder nur
> [mm]T(1)=1, T(2) = 1, T(3) =1[/mm]?
Gruß
meili
|
|
|
|
