Lösen von Rekursionsgleichung

Neue Frage »

djuus Auf diesen Beitrag antworten »
Lösen von Rekursionsgleichung
Meine Frage:
Hi, kann mir jemand helfen die folgende Rekursionsgleichung zu lösen:

T(n) = T(n - 1) * 2 T(n - 2) für n0 > 10 und T(10) = 1



Danke schon mal

Meine Ideen:
Das Mastertheorem lässt sich leider nicht anwenden und auch einen Rekursionsbaum stelle ich mir, wegen den beiden unterschiedlichen rekursiven Aufrufen mit n - 1 und n - 2, schwer vor. Außerdem scheinen keine Kosten pro Ebene anzufallen.
Math1986 Auf diesen Beitrag antworten »
RE: Lösen von Rekursionsgleichung
Hier fehlt ein Wert, um die Reihe eindeutig zu bestimmen.
djuus Auf diesen Beitrag antworten »
RE: Lösen von Rekursionsgleichung
mh.. ich hatte diese Aufgabe vor ein paar Tagen in einer Klausur und konnte sie nicht lösen. Dann wäre wahrscheinlich die richtige Antwort gewesen, dass sie nicht lösbar ist?!

Naja, danke auf jeden fall smile
Karlito Auf diesen Beitrag antworten »

Ich habe mir die Aufgabe auf dem Informatikerboard mal angeschaut aber noch nciht weiter bearbeitet. Ich stecke leider nicht mehr so sehr in dem Thema drin.

T(n) ist eine beschreibung der Laufzeit eines Programmes in abhängigkeit von sich selbst. D.h. das Programm ruft sich selbst rekursiv wieder auf.

Das ganze wurde dann immer so gelöst, dass man die Definition von T(n) rekursiv wieder einsetzt (2-3 mal) und daraus dann eine Bildungsvorschrift in Abhhängigkeit von n ableiten kann.

Ziel des ganzen ist eine Komplexitätsabschätzung für das Laufzeitverhalten (Landau-Symbole), wobei möglichst Theta gefunden werden soll (wenn es eins gibt).

Ich könnte mir vorstellen, dass dies ein Spezialbgebiet ist, mit dem sich hier nicht viele Auskennen. Sobald ich mein Motivationstief überwunden habe, werde ich mich auch noch mal dran setzen.

Nach dem was ich bisher gemacht habe sieht aber alles nach exponentieller Laufzeit aus...

VG,

Karlito
djuus Auf diesen Beitrag antworten »
RE: Lösen von Rekursionsgleichung
So ich bin mittlerweile davon überzeugt, dass meine Erinnerung mir einen Streich gespielt hat und die Aufgabe T(n) = T(n - 1) + 2 T(n - 2) lautete. Sorry für die Verwirrung.
Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »