Hilfe bei Rekursionsgleichung < Folgen und Reihen < eindimensional < reell < Analysis < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 20:25 Do 29.05.2008 | | Autor: | Sharadix |
Hallo, ich benötige Hilfe zur Lösung einer Rekursionsgleichung. Per Master-Theorem(falls das wem was sagt), komme ich irgendwie auf keinen grünen Nenner. Ich glaube die Aufgabe lässt sich leider nicht mit dem Master-Theorem lösen....
Jetzt habe ich mal versucht die ersten paar Folgeglieder auszurechnen um dort irgend ein Muster zu erkennen. Ich habe n durch [mm] 2^n [/mm] ersetzt, damit man beim teilen von T(n/2) keinen nonsense bekommt.
Also hier mal mein Ansatz:
T(n)=2*T(n/2)+c*n*log(n)
[mm] T(2^n)=2*T(2^{n-1})+c*2^n*(log(2^n))
[/mm]
[mm] T(2^0)=1
[/mm]
[mm] T(2^1)=(2*1)+c*2^1(log(2^1))=
[/mm]
[mm] T(2^2)=2*( 2+c*2^1*(log(2^1)))+c*2^2*(log(2^2))
[/mm]
[mm] T(2^3)=2*(2*( 2+c*2^1*(log(2^1)))+c*2^2*(log(2^2)))+c*2^3*(log(2^3))
[/mm]
[mm] f(2^n)?
[/mm]
f(n)?
Ja, leider, wie man sieht ist mir das Muster leider verborgen geblieben.
Falls jemand einen besseren Vorschlag hat, wie ich bei der Aufgabe ans Ziel komme, (also andere angehensTaktik) oder falls mir jemand bei meinem Ansatz helfen könnte (im Falle des Falles, der Anfang und die Strategie stimmt so), dann tue er bitte Kund :). Ich bin grade mal wieder am Verzweifeln und Haare verlieren und wäre im Sinne meines eigenen Wohlergehens und dem meiner immer lichter werdenden Haare sehr dankbar.
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 07:48 Fr 30.05.2008 | | Autor: | Loddar |
Hallo Sharadix!
Um ein Muster erkennen zu können, musst Du die einzelnen Term [mm] $T\left(2^n\right)$ [/mm] auch mal ausrechnen / zusammenfassen.
Da habe ich dann erhalten:
[mm] $$T\left(2^1\right) [/mm] \ = \ [mm] 2*\left[1+1*c*\log(2)\right]$$
[/mm]
[mm] $$T\left(2^2\right) [/mm] \ = \ [mm] 4*\left[1+3*c*\log(2)\right]$$
[/mm]
[mm] $$T\left(2^3\right) [/mm] \ = \ [mm] 8*\left[1+6*c*\log(2)\right]$$
[/mm]
[mm] $$T\left(2^4\right) [/mm] \ = \ [mm] 16*\left[1+10*c*\log(2)\right]$$
[/mm]
[mm] $$\vdots$$
[/mm]
[mm] $$T\left(2^n\right) [/mm] \ = \ [mm] 2^n*\left[1+c*\log(2)*\summe_{k=1}^{n}k\right] [/mm] \ = \ [mm] 2^n*\left[1+\bruch{n*(n+1)}{2}*c*\log(2)\right]$$
[/mm]
Gruß
Loddar
|
|
|
|
