Fibonacci-Zahlenpaare

Wir haben oben den exponentiellen Aufwand bei der rekursiven Berechnung der Fibonacci-Zahlen dadurch reduziert, daß wir uns über den Zusammenhang der benötigten Teilprobleme einen Überblick verschafft und die Teilprobleme dann von unten herauf gelöst hatten, gemäß der Vorgehensweise der Dynamischen Programmierung . Dabei sind wir auf eine iterative Lösung gestoßen, und nach der "herrschenden Meinung " kommt daher der nun nur noch lineare Aufwand.

Tatsächlich ist dies aber gar nicht der Fall, wie wir zeigen können: es gibt eine rekursive  Lösung des Problems, die ebenfalls linearen  Aufwand besitzt, also bis auf einen (allerdings recht großen!) konstanten Faktor ebenso effizient ist wie unsere iterative Lösung.

Der Kern unseres Ansatzes liegt in der Beobachtung, daß unsere Rekursionsgleichung

(1) F(n) = F(n-1) + F(n-2) für n > 2
(2) F(1) = F(2) = 1
immer unmittelbar benachbarte Fibonacci-Zahlen verknüpft; fassen wir sie zu Paaren zusammen, so bekommen wir für zwei benachbarte Paare eine einstufige Rekursionsbeziehung:
Paare
oder auch
Paare2
mit einer konstanten Matrix A. Schon hier kann man sehen, daß wir jetzt nur noch (n) Teilprobleme zu lösen haben, und jeder Schritt bringt einen konstanten Beitrag, also ist der gesamte Aufwand höchstens linear!

Es gibt einen Trick, mit dem man die Gleichung für G(n) sogar mit logarithmischem  Aufwand direkt lösen kann!

zurück | Inhalt | Index | vor | Vorlesung
Klaus Lagally, 22. Februar 2000, 19:36