Hallo,
ich habe gerade auf http://www-lehre.informatik.uni-osnabrueck.de/~ainf/2000/skript/node39.html
gelesen, dass die Fibonacci Zahlen eine Laufzeit von O(1.62n) haben, wobei n der Wert des Inputs ist, nicht seine Länge.
Warum ist das so und wie kommt man darauf?
Danke!
Hallo,
ich habe gerade auf http://www-lehre.informatik.uni-osnabrueck.de/~ainf/2000/skript/node39.html
gelesen, dass die Fibonacci Zahlen eine Laufzeit von O(1.62n) haben, wobei n der Wert des Inputs ist, nicht seine Länge.
Warum ist das so und wie kommt man darauf?
Danke!
Die Herleitung unten gelesen?
Wenn man fib(n) = fib(n-1) + fib(n-1) rechnen würde, hätte man O(2n), da jedes mal wenn man eine "Ebene" tiefer geht, sich die Anzahl der Berechnungen verdoppelt.
Nun steht da aber fib(n) = fib(n-1) + fib(n-2) (Wie es ja auch richtig ist ;))
Aber es muss auf jeden Fall in der Größenordnung an liegen. (Frage nur, wie groß ist a)
Für fib(n) braucht man an Rechenschritte.
Für fib(n-1) braucht man an-1 Rechenschritte.
Für fib(n-2) braucht man an-2 Rechenschritte.
fib(n) kann man aber ja auch schreiben als fib(n-1) + fib(n-2). Man braucht also fib(n) a[sup]n-1[Sup] + an-2 Rechenschritte und dann noch einen Rechenschritt um die Zahlen zu addieren.
Damit ergibt sich dann die formel: an = an-1 + an-2 + 1.
Dann teilt man durch an-2:
a2 = a + 1+ 1/an-2
Da man bei der Gross O Notation nur die asymptotischen Laufzeiten betrachtet, schaut man sich den Fall n gegen unendlich an, dann fällt der Term 1/an-2 weg und es bleibt übrig:
a2 = a + 1 bzw
0 = -a2 + a + 1
Das ist jetzt eine quadratische Gleichung, die man mittels pq Formel lösen kann. Dabei bekommt man 2 Werte raus, der negative interessiert nicht. Der positive ist dann 1,62.
Noch fragen? ;)