Man kriegt das auch noch effektiver hin. Und damit willkommen beim
DP-Fibonacci-Effizienzkontest!
Heute im Ring: Die iterative Variante, die Standard-Rekursive mit Buffer und eine etwas "aufpoliert" eigene rekursive Variante, auch mit Buffer. Dem Borg seine O(1)-Lösung sei hier außen vor gelassen, die ist ja geschummelt.
Die aufpolierte Fassung macht nichts anderes, als fib(n) = fib(n-1) + fib(n-2) aufzudröseln, denn fib(n-1) ist ja nichts anderes als fib(n-2)+fib(n-3), also ist fib(n) = 2*fib(n-2)+fib(n-3) was dann wieder 3*fib(n-3)+2*fib(n-4) entspricht. Die Koeffizienten sind wiederum Fibonaccizahlen, da allerdings aufsteigende. Das ganze trifft sich dann in der Mitte, und ergibt sich, je nach Teilbarkeit von n durch 2, entweder zu fib(n) = fib(n div 2)*(fib(n div 2 +1)+fib(n div 2 -1)) für ungerade n, oder fib((n+1) div 2)²+fibOwn(n div 2)², was jede Menge Aufrufe spart und das ganze zumindest in dieser Implementation 10 mal schneller als den Iterativen macht.
Und die Testergebnisse für fib(10000) befinden sich, ebenso wie der (schnell'n'dreckige) Code, im Anhang. Die Zahlen in den ProgressBars ist die jeweilige Dauer in ms. Benutzt wird eine olle BigInt-Klasse, weil die da rauskommenden Zahlen doch etwas größer als 2^63-1 sind.
aber vermutlich geht das ganze noch ein Tucken schneller, ich bin gespannt
