exponentielle Laufzeit
-
Hallo Leute,
ich hab mal eine Frage zu folgender Laufzeitsfunktion:
f(n) = a * f(n-1) + a * f(n-2)
n ... Element der natürlichen Zahlen
a > 0 ... KonstanteBetrachtet werden müssten nur alle n >= 11
Die Frage zu der Funktion ist, für welche Werte von dem a die Funktion f(n) exponentiell wächst?
Bis jetzt konnte ich nur herausfinden, dass das wahrscheinlich irgendwas mit der Fibonacci-Folge zu tun haben muss.
http://de.wikipedia.org/wiki/Fibonacci-Folge
Was das jetzt mit a auf sich hat, versteh ich nicht so richtig...
Kann mir jemand bei meinem Problem helfen oder einen Tipp geben?
-
Was soll da exponentiell steigen, die Laufzeit oder der Funktionswert?
-
Gemeint ist die Laufzeit von f(n) bzw. für welche Werte von a das f(n) exponentiell wächst.
-
Verbessert mich, wenn ich falsch liege, aber:
f(n) = a (f(n-1) + f(n-2))
Konstanten und konstante Faktoren kann man weglassen (entscheidend ist für soetwas die grobe "Richtung"):
f(n) = f(n-1) + f(n-2)Die Konstante hat also keinerlei Einfluss(wieso auch? 2*ex ist genauso exponentialfunktion wie ex)
Ob das überhaupt exponentiell wächst klärt die nicht-rekursive Funktion.
Ich bin zu faul, die hier reinzupacken:
http://de.wikipedia.org/wiki/Fibonacci-Folge#Formel_von_Moivre-Binet
Da sieht man das man einen Bruch hoch n hat, also einen exponentiellen Zusammenhang.Aber exponential ist es für alle a.
Mfg
-
...
-
Gemeint ist die Laufzeit von f(n) bzw. für welche Werte von a das f(n) exponentiell wächst.
Die Laufzeit fuer die Berechnung ist nicht gleich dem Wachstum der Funktion.
-
Meine Vermutung: Man kann durch Induktion zeigen dass f(n) = a^n*F(n) wobei F(n) die bekannte Fibonaccifolge ist. Hilft das weiter?
-
Ich würd mir die explizite Formel von wolframalpha berechnen lassen, beweisen und mit dieser weiterarbeiten.
-
DerBaer_ schrieb:
Verbessert mich, wenn ich falsch liege
Du liegst falsch. Der Faktor a wird in jedem Induktionsschritt reinmultipliziert. d.h. F(11) hat schon ein a^11 als Vorfaktor. Wie du siehst, hat a also einen riesigen Einfluss.
Mein Tipp: für a>=1 hat das Ganze auf jeden Fall exponentielle Steigung. Die Frage ist nun, wie klein das a sein muss, damit dies nicht mehr gilt, da die Fibonaccifolge selbst exponentiell ansteigt.
Als Untere Schranke dieses a würde ich nach Moivre-Binet a>=2/(1+sqrt(5)) setzen. Denn dann kürzt dies den größeren Summand auf 1 und der kleinere Summand geht gegen 0 wenn n->unendlich.
Wenn man die Formel von Moivre-Binet nicht kennt, sucht man sich die passende Formel zur Berechnung der Konvergenzeigenschaft aus und sucht das größte a bei dem die Reihe noch konvergiert.