Rekursive Folge < Folgen und Reihen < eindimensional < reell < Analysis < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 17:02 So 08.04.2012 | | Autor: | bandchef |
| Aufgabe | Aufgabe: Bestimmen Sie die exakte Schranke für die folgende Rekursionsgleichung mit Hilfe der Iterations- oder Substitutionsmethode:
$ T(1)=1; T(2)=1; T(3) = 1; T(n) = [mm] 2T(n-1)n^2, \forall [/mm] n > 3$ |
Hi Leute!
Ich hab dazu in meinem Buch ein Beispiel:
$ T(1)=1; T(n) = 2T(n-1)+1$
Dort wurde die Iterationsmethode angewendet:
$T(n) = 2T(n-1)+1 =<br /> 2(2T(n-2)+1)+1 =<br /> 2(2(2T(n-3)+1)+1)+1 =<br /> 2^3T(n-3)+(1+2+4) = ... =<br /> 2^iT(n-i) + [mm] \sum_{k=0}^{i-1} 2^k$
[/mm]
Ich würde nun gerne dieses Beispiel auf meine fast gleiche Übungsaufgabe anwenden wollen. Ich weiß aber bzw. sehe nicht so recht, wo da was eingesetzt wurde... Ich hab's aber mal probiert:
$<br /> T(n) = [mm] 2T(n-1)+n^2
Stimmt das soweit? Das einzige Problem ist jetzt noch, dass ich nicht weiß ob ich die Summe am Ende des Terms richtig konstruiert hab... Als Summenergebnis brauch ich 1,3,5,7,15,...
Könnt ihr mir weiterhelfen?
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 17:23 So 08.04.2012 | | Autor: | Fulla |
> Aufgabe: Bestimmen Sie die exakte Schranke für die
> folgende Rekursionsgleichung 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 \geq 3[/mm]
>
>
>
> Hi Leute!
>
>
> Ich hab dazu in meinem Buch ein Beispiel:
>
> [mm]T(1)=1; T(n) = 2T(n-1)+1[/mm]
>
> Dort wurde die Iterationsmethode angewendet:
>
> [mm]T(n) = 2T(n-1)+1 = 2(2T(n-2)+1)+1 = 2(2(2T(n-3)+1)+1)+1 = 2^3T(n-3)+(1+2+4) = ... = 2^iT(n-i) + \sum_{k=0}^{i-1} 2^k[/mm]
>
>
> Ich würde nun gerne dieses Beispiel auf meine fast gleiche
> Übungsaufgabe anwenden wollen. Ich weiß aber bzw. sehe
> nicht so recht, wo da was eingesetzt wurde... Ich hab's
> aber mal probiert:
>
> [mm] T(n) = 2T(n-1)+n^2 = 2(2T(n-2)+n^2)+n^2 = 2(2(2T(n-3)+n^2)+n^2)+n^2 = 2(2(2(2T(n-3)+n^2)+n^2)+n^2)+n^2 = 2^iT(n-i) + \left(\sum_{k=2}^{i} \left(2^{k-1}\right)\right)n^2[/mm]
Hallo bandchef,
wenn du [mm]T(n-1)[/mm] durch [mm]T(n-2)[/mm] ausdrückst, muss da ein [mm](n-1)^2[/mm] statt [mm]n^2[/mm] stehen, also [mm]T(n-1)=2 T(n-2) + (n-1)^2[/mm].
Insgesamt hast du dann
[mm]T(n)=2*T(n-1)+n^2=2*2*T(n-2) +(n-1)^2+n^2=\ldots [/mm]
Lieben Gruß,
Fulla
> Stimmt das soweit? Das einzige Problem ist jetzt noch, dass
> ich nicht weiß ob ich die Summe am Ende des Terms richtig
> konstruiert hab... Als Summenergebnis brauch ich
> 1,3,5,7,15,...
>
> Könnt ihr mir weiterhelfen?
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 17:29 So 08.04.2012 | | Autor: | bandchef |
$ [mm] T(n)=2\cdot{}T(n-1)+n^2=2\cdot{}2\cdot{}T(n-2) +(n-1)^2+n^2=\ldots [/mm] $
Fehlt da jetzt nicht eine Klammer?
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 17:44 So 08.04.2012 | | Autor: | Fulla |
Hallo nochmal,
> [mm]T(n)=2\cdot{}T(n-1)+n^2=2\cdot{}\red{(}2\cdot{}T(n-2) +(n-1)^2\red{)}+n^2=\ldots[/mm]
>
> Fehlt da jetzt nicht eine Klammer?
Ja, da hast du natürlich recht!
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 17:50 So 08.04.2012 | | Autor: | bandchef |
Wenn ich deinen Tip jetzt weiter fortführe, dann komm ich auf das hier:
[mm] T(n)=2\cdot T(n-1)+n^2=
[/mm]
[mm] 2\cdot(2\cdot [/mm] T(n-2 [mm] +(n-1)^2)+n^2=
[/mm]
[mm] 2\cdot(2\cdot(2\cdot T(n-3)+(n-2)^2)+(n-1)^2)+n^2=
[/mm]
[mm] 2\cdot(2\cdot(2\cdot(2\cdot T(n-4)+(n-3)^2)+(n-2)^2)+(n-1)^2)+n^2= [/mm] ... = ?
Wenn ich das ganze jetzt noch ausmultipliziert hinschreibe, dann sollte es so aussehen:
T(n) = [mm] 2T(n-1)+n^2 [/mm] =
[mm] 4T(n-2)+2(n-1)^2+n^2=
[/mm]
[mm] 8T(n-3)+4(n-2)^2+2(n-1)^2+n^2=
[/mm]
[mm] 16T(n-4)+8(n-3)^2+4(n-2)^2+2(n-1)^2+n^2 [/mm] = ... = ?
Jetzt muss ich das ja jetzt noch zu einer allgemeinen Formel zusammenfassen, damit man quasi die Laufzeit ablesen kann. Aber da komm ich jetzt irgendwie gar nicht mehr zurecht...; außer, dass ganz am Anfang wie bei meiner ersten "Lösung" so ein [mm] $2^i$ [/mm] stehen müsste.
Kannst du mir da nochmal helfen?
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 18:21 So 08.04.2012 | | Autor: | leduart |
Hallo
im ersten post hattest du
T(n) = [mm] 2T(n-1)n^2, \forall [/mm] n [mm] \geq [/mm] 3
war das ein Tipfehler?
weiter angenommen T(n) = [mm] 2T(n-1)+n^2, \forall [/mm] n [mm] \geq [/mm] 3
dann schreib mal dein 4 tes Ding ausgerechnet hin_ fang an ,mit [mm] n^2+2*(n-1)^2+...
[/mm]
und dann versuch mal selbst eine formel zu finden. di lernst es NIE durch vormachen, sondern man muss halt mal Formeln umschreiben, dann ne vermutung, dann noch einen Schritt weiter und sehen. öb die vermutung stimmt, schlimmstenfalls noch einen Schritt und du kriegst das hin. dass da [mm] 2^i [/mm] (was ist i) steht ist nicht sehr viel gedacht.
gruss leduart
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 18:25 So 08.04.2012 | | Autor: | bandchef |
Oh, das ist natürlich ein Tipfehler!!! Es muss heißen: $T(n) = [mm] 2T(n-1)+n^2$
[/mm]
T(n) = $ [mm] 2T(n-1)+n^2 [/mm] $ =
$ [mm] 4T(n-2)+2(n-1)^2+n^2= [/mm] $
$ [mm] 8T(n-3)+4(n-2)^2+2(n-1)^2+n^2= [/mm] $
$ [mm] 16T(n-4)+8(n-3)^2+4(n-2)^2+2(n-1)^2+n^2 [/mm] $ = [mm] 2^iT(n-i)+\sum_{k=0} ^{i-1}\left(2^k\cdot (n-k)^2\right)
[/mm]
So sollte doch die Summe nun passen 
|
|
|
| |
|
Hallo bandchef,
> Oh, das ist natürlich ein Tipfehler!!! Es muss heißen:
> [mm]T(n) = 2T(n-1)+n^2[/mm]
>
>
> T(n) = [mm]2T(n-1)+n^2[/mm] =
> [mm]4T(n-2)+2(n-1)^2+n^2=[/mm]
> [mm]8T(n-3)+4(n-2)^2+2(n-1)^2+n^2=[/mm]
> [mm]16T(n-4)+8(n-3)^2+4(n-2)^2+2(n-1)^2+n^2[/mm] =
> [mm]2^iT(n-i)+\sum_{k=0} ^{i-1}\left(2^k\cdot (n-k)^2\right)[/mm]
>
>
> So sollte doch die Summe nun passen
Ja, jetzt passt die Summe.
Gruss
MathePower
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 19:37 So 08.04.2012 | | Autor: | bandchef |
Wenn ich nun die Rekursionsbasis aus meiner Summe ablese, dann komm ich auf das hier:
Rekursionsbasis wird erreicht, wenn: $n-i=1$. Setze also: $i=n-1$.
$ [mm] 2^{n-1}T(n-(n-1))+\sum_{k=0} ^{(n-1)-1}\left(2^k\cdot (n-k)^2\right) [/mm] = [mm] 2^{n-1}T(1)+\sum_{k=0}^{n-2}\left(2^k\cdot (n-k)^2\right) [/mm] = [mm] 2^{n-1}+\sum_{k=0}^{n-2}\left(2^k\cdot (n-k)^2\right)$ [/mm] Jetzt müsste ich die Summe noch etwas umformen, aber das versteh ich nicht...; könnt ihr mir da helfen?
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 19:47 So 08.04.2012 | | Autor: | leduart |
Hallo
das hat nichts mit Verstehen zu tun, wenn man nicht einfach mal umformt. sogar n-1-1 lässt du stehen.
Du musst dich wirklich länger dran setzen und selber arbeiten!
Gruss leduart
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 19:50 So 08.04.2012 | | Autor: | bandchef |
Bitte lies mal meine letzte Frage nochmal. Da hab ich einiges editiert. Jetzt hab ich zumindestens schon mal das gemacht, was du grad geschrieben hast. Ich hab's quasi jetzt soweit vereinfacht, bis ich wirklich nur noch die Summe dastehen hab. Da weiß ich nun wirklich nicht mehr weiter... Ich muss quasi jetzt den Summenausdruck in einen Term umwandeln. Das weiß ich nicht wie das geht...
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 19:52 So 08.04.2012 | | Autor: | leduart |
Hallo
ich seh grad die Formel gilt nur für n>3 also kannst du ja nicht bis n-i=1 gehen!
Gruss leduart
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 19:53 So 08.04.2012 | | Autor: | bandchef |
Die Formel gilt für [mm] $n\geq3$..., [/mm] oder?
Darf ich bis $n-i=3 [mm] \Leftrightarrow [/mm] i=n-3$ gehen?
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 19:59 So 08.04.2012 | | Autor: | leduart |
Hallo
das hast DU in der Aufgabenstellung geschrieben, aber auch
T(3)=1. Sieh nach, ob das stimmen kann, wenn du T(3) aus T(2) nach der Formel bestimmst.
Gruss leduart
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 20:02 So 08.04.2012 | | Autor: | bandchef |
Verdammt. Tipfehler. Es heißt in der Tat n>3. Ich werde es im Ausgangspost ändern!
Wie liest man nun die korrekte Rekursionsbasis ab?
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 21:15 So 08.04.2012 | | Autor: | leduart |
Hallo
denk nach, welches T man als erstes einsetzen kann! Das ist die Basis.
In irgendwelchen vverbesserten posts rumzusuchen hab ich keine Lust, poste die Lösung mit Herleitung in einem post.
gruss leduart
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 11:17 Mo 09.04.2012 | | Autor: | bandchef |
$ T(1)=1; T(2)=1; T(3) = 1; T(n) = [mm] 2T(n-1)n^2, \forall [/mm] n > 3 $
$T(n) = [mm] 2T(n-1)+n^2 [/mm] $ =
$ [mm] 4T(n-2)+2(n-1)^2+n^2= [/mm] $
$ [mm] 8T(n-3)+4(n-2)^2+2(n-1)^2+n^2= [/mm] $
$ [mm] 16T(n-4)+8(n-3)^2+4(n-2)^2+2(n-1)^2+n^2 [/mm] $ = $ [mm] 2^iT(n-i)+\sum_{k=0} ^{i-1}\left(2^k\cdot (n-k)^2\right) [/mm] $
Rekursionsbasis wird erreicht, wenn: $ n-i=1 $. Setze also: $ i=n-1 $.
$ [mm] 2^{n-1}T(n-(n-1))+\sum_{k=0} ^{(n-1)-1}\left(2^k\cdot (n-k)^2\right) [/mm] = [mm] 2^{n-1}\underbrace{T(1)}_{=1}+\sum_{k=0}^{n-2}\left(2^k\cdot (n-k)^2\right) [/mm] = [mm] 2^{n-1} [/mm] + [mm] \underbrace{\sum_{k=0}^{n-2}\left(2^k\cdot (n-k)^2\right)}_{\text{in Term umwandeln}} [/mm] = ... $
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 11:37 Mo 09.04.2012 | | Autor: | leduart |
Hallo
Gerade hast du festgestellt, dass die Formel nicht für n=1,2,3 gilt wieso kannst du dann n-i=1 setzen?
Gruss leduart
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 12:08 Mo 09.04.2012 | | Autor: | bandchef |
Also muss ich die Formel n-i=4 setzen?
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 17:30 Mo 09.04.2012 | | Autor: | leduart |
Hallo
Denk! welches kleinste n kannst du einsetzen und kriegst n+1 richtig raus. woher kennst du denn T(4) wenn du das als Anfang nehmen willst.Ein bissel mehr selber denken würde dir nicht schaden. Ich schenk dir ein großers Osterei voll Nachdenkzeit.
Wenn du so was schreibst, solltest du immer einen Grund angeben, der dich selbst 100% überzeugt- und nicht einfach ne Vermutung
gruss leduart
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 20:24 Mo 09.04.2012 | | Autor: | bandchef |
Naja, dann probier ich's nochmal:
T(1)=1 ist ja das kleinste n das ich einsetzen kann und da weiß ich auch was rauskommt. Also muss ich sagen, $n-i=1 [mm] \Leftrightarrow [/mm] i=n-1$, und das hab ich ja schon mal geschrieben, oder? Und das wurde auch als falsch bezeichnet...; von daher weiß ich ehrlich gesagt nich mehr was ich sonst noch einsetzen soll. Es bleiben mir jetzt nur noch T(2) und T(3), aber das erscheint mir auch eher unpassend, da es ja nicht das kleinste n ist...
Ich würd mich freun, wenn du mich jetzt nochmal genauer drüber aufklären könntest!
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 22:20 Mo 09.04.2012 | | Autor: | leduart |
Hallo
wenn du T(1) einsetzt kommt T(2) falsch raus. Wenn du T(2) einsetzt kommt T(3) falsch raus, denn die Formel gilt ja erst ab n>3
wenn du T(3) einsetzt kommt T(4) richtig raus also ist der Anfang T(3). warum kannst du genauso nicht selbst überlegen.
Gruss leduart
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 15:14 Di 10.04.2012 | | Autor: | bandchef |
Also sieht das ganze nun so aus:
$ T(1)=1; T(2)=1; T(3) = 1; T(n) = [mm] 2T(n-1)n^2, \forall [/mm] n > 3 $
$ T(n) = [mm] 2T(n-1)+n^2 [/mm] $ =
$ [mm] 4T(n-2)+2(n-1)^2+n^2= [/mm] $
$ [mm] 8T(n-3)+4(n-2)^2+2(n-1)^2+n^2= [/mm] $
$ [mm] 16T(n-4)+8(n-3)^2+4(n-2)^2+2(n-1)^2+n^2 [/mm] $ = $ [mm] 2^iT(n-i)+\sum_{k=0} ^{i-1}\left(2^k\cdot (n-k)^2\right) [/mm] $
Rekursionsbasis wird erreicht, wenn: $ n-i=3 $. Setze also: $ i=n-3 $.
$ [mm] 2^{n-3}T(n-(n-3))+\sum_{k=0} ^{(n-3)-1}\left(2^k\cdot (n-k)^2\right) [/mm] = [mm] 2^{n-3}\underbrace{T(3)}_{=1}+\sum_{k=0}^{n-4}\left(2^k\cdot (n-k)^2\right) [/mm] = [mm] 2^{n-3} [/mm] + [mm] \underbrace{\sum_{k=0}^{n-4}\left(2^k\cdot (n-k)^2\right)}_{\text{in Term umwandeln}} [/mm] = ... $
So, da ja jetzt die Rekursionsbasis stimmt, muss ich noch die Summe in einen Term umwandeln. Das weiß ich ebenfalls nicht wie das gehen soll...
|
|
|
| |
|
Hallo bandchef,
> Also sieht das ganze nun so aus:
>
>
> [mm]T(1)=1; T(2)=1; T(3) = 1; T(n) = 2T(n-1)n^2, \forall n > 3[/mm]
>
>
> [mm]T(n) = 2T(n-1)+n^2[/mm] =
> [mm]4T(n-2)+2(n-1)^2+n^2=[/mm]
> [mm]8T(n-3)+4(n-2)^2+2(n-1)^2+n^2=[/mm]
> [mm]16T(n-4)+8(n-3)^2+4(n-2)^2+2(n-1)^2+n^2[/mm] =
> [mm]2^iT(n-i)+\sum_{k=0} ^{i-1}\left(2^k\cdot (n-k)^2\right)[/mm]
>
>
> Rekursionsbasis wird erreicht, wenn: [mm]n-i=3 [/mm]. Setze also:
> [mm]i=n-3 [/mm].
> [mm]2^{n-3}T(n-(n-3))+\sum_{k=0} ^{(n-3)-1}\left(2^k\cdot (n-k)^2\right) = 2^{n-3}\underbrace{T(3)}_{=1}+\sum_{k=0}^{n-4}\left(2^k\cdot (n-k)^2\right) = 2^{n-3} + \underbrace{\sum_{k=0}^{n-4}\left(2^k\cdot (n-k)^2\right)}_{\text{in Term umwandeln}} = ...[/mm]
>
> So, da ja jetzt die Rekursionsbasis stimmt, muss ich noch
> die Summe in einen Term umwandeln. Das weiß ich ebenfalls
> nicht wie das gehen soll...
Multipliziere den Ausdruck unter dem Summenzeichen aus.
Betrachte dann
[mm]\summe_{k=0}^{n-4}x^{k}=\bruch{x^{n-3}-1}{x-1}[/mm]
Differenziere dies 2mal und setze die Ergebnisse für die einzelnen
Partialsummen ein, wobei für x=2 zu setzen ist.
Gruss
MathePower
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 15:46 Di 10.04.2012 | | Autor: | bandchef |
$ ... = [mm] 2^{n-3} [/mm] + [mm] \sum_{k=0}^{n-4}\left(2^k\cdot (n-k)^2\right) [/mm] = [mm] 2^{n-3} [/mm] + [mm] \sum_{k=0}^{n-4}\left( 2^kn^2-2\cdot 2^k k n + 2^k k^2 \right) [/mm] = ...$
Diesen "neuen" Ausdruck unter dem Summenzeichen soll ich 2-mal differenzieren? Nach welcher Variable soll ich differenzieren? Nach k oder nach n?
Warum muss ich dann eigentlich die geometrische Reihe betrachten? Das verstehe ich noch nicht so ganz...
|
|
|
| |
|
Hallo bandchef,
> [mm]... = 2^{n-3} + \sum_{k=0}^{n-4}\left(2^k\cdot (n-k)^2\right) = 2^{n-3} + \sum_{k=0}^{n-4}\left( 2^kn^2-2\cdot 2^k k n + 2^k k^2 \right) = ...[/mm]
>
> Diesen "neuen" Ausdruck unter dem Summenzeichen soll ich
> 2-mal differenzieren? Nach welcher Variable soll ich
> differenzieren? Nach k oder nach n?
>
Setzt man für [mm]2^{k}=x^{k}[/mm] dann steht da:
[mm]\sum_{k=0}^{n-4}\left(x^k\cdot (n-k)^2\right) = \sum_{k=0}^{n-4}\left( x^k*n^2-2\cdot x^k *k*n + x^{k}*k^2 \right) = ...[/mm]
Weder noch.
Ich habe doch geschrieben:
Betrachte
[mm]\summe_{k=0}^{n-4}x^{k}=\bruch{x^{n-3}-1}{x-1}[/mm]
Diesen Ausdruck diffenzierst Du 2 mal.
> Warum muss ich dann eigentlich die geometrische Reihe
> betrachten? Das verstehe ich noch nicht so ganz...
Um die Summen
[mm]\summe_{k=0}^{n-4}k*2^{k}, \ \summe_{k=0}^{n-4}k^{2}*2^{k}[/mm]
berechnen zu können.
Gruss
MathePower
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 16:11 Di 10.04.2012 | | Autor: | bandchef |
Wenn ich $ [mm] \summe_{k=0}^{n-4}x^{k}=\bruch{x^{n-3}-1}{x-1} [/mm] $ 2 mal nach x differenziere, dann bekomm ich wahnsinnig großen Bruchterm..., der sieht so aus:
[mm] $\frac{x^{n-3}ln(x)(n-3)}{x(x-1)}+\frac{x^{n-3}}{x(x-1)}-\frac{x^{n-3}ln(x)}{(x-1)^2}$
[/mm]
|
|
|
| |
|
Hallo bandchef,
> Wenn ich [mm]\summe_{k=0}^{n-4}x^{k}=\bruch{x^{n-3}-1}{x-1}[/mm] 2
> mal nach x differenziere, dann bekomm ich wahnsinnig
> großen Bruchterm..., der sieht so aus:
>
> [mm]\frac{x^{n-3}ln(x)(n-3)}{x(x-1)}+\frac{x^{n-3}}{x(x-1)}-\frac{x^{n-3}ln(x)}{(x-1)^2}[/mm]
Das stimmt nicht.
Rechne das mal vor.
Gruss
MathePower
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 16:23 Di 10.04.2012 | | Autor: | bandchef |
[mm] $f(x)=\frac{x^{n-3}-1}{x-1}$
[/mm]
$f'(x) = [mm] \frac{\frac{x^{n-3}(n-3)}{x}(x-1)-(x^{n-3}-1)}{(x-1)^2}
[/mm]
|
|
|
| |
|
Hallo bandchef,
> [mm]f(x)=\frac{x^{n-3}-1}{x-1}[/mm]
>
> $f'(x) = [mm]\frac{\frac{x^{n-3}(n-3)}{x}(x-1)-(x^{n-3}-1)}{(x-1)^2}[/mm] ![[ok]](/images/smileys/ok.gif "[ok]")
[mm]=\frac{(n-3)x^{n-4}(x-1)-x^{n-3}+1}{(x-1)^2}=\frac{(n-4)x^{n-3}-(n-3)x^{n-4}+1}{(x-1)^2}[/mm]
Und das nochmal ableiten.
Gruß
schachuzipus
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 16:41 Di 10.04.2012 | | Autor: | bandchef |
[mm] $f''(x)=\frac{(n-4)(n-3)x^{n-4}-(n-4)(n-3)x^{n-5}-(((n-4)x^{n-3}-(n-3)x^{n-4}-1)(2x-2))}{(x-1)^4}$
[/mm]
|
|
|
| |
|
Hallo nochmal,
>
> [mm]f''(x)=\frac{(n-4)(n-3)x^{n-4}-(n-4)(n-3)x^{n-5}-(((n-4)x^{n-3}-(n-3)x^{n-4}-1)(2x-2))}{(x-1)^4}[/mm]
Nicht ganz!
Bei den ersten beiden Summanden musst du eine dicke Klammer drum machen und noch mit [mm] $(x-1)^2$ [/mm] multiplizieren und hinten würde ich $2(x-1)$ als Faktor stehen lassen.
Dann kannst du nämlich im Zähler $(x-1)$ ausklammern und einmal wegkürzen.
Bei gebr.-rat. Funktionen erhöht sich der Exponent im Nenner mit jeder weiteren Ableitung um 1, wenn du ordentlich zusammenfasst ...
Gruß
schachuzipus
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 19:26 So 08.04.2012 | | Autor: | bandchef |
Damit ich jetzt die exakte Schranke [mm] $\Theta$ [/mm] der Laufzeit dieses Algorithmus berechnen kann, heißt es in meinem Buch, man muss die Rekursionsbasis erreichen.
Leider wird in meinem Buch nicht weiter darauf eingegangen, was die Rekursionsbasis ist. Könnt ihr mir das sagen? Wie kommt man auf die Rekursionsbasis?
Edit: Die Frage war eigentlich auf die letzte Antwort gedacht...
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 19:54 So 08.04.2012 | | Autor: | leduart |
Hallo
da wo man anfängt, hier bei n=3 oder 4 also beim kleinsten n ab dem die Formel gilt.
aber das ist doch eigentlich klar oder wie will man sonst T(n) berechnen?
Gruss leduart
|
|
|
|
