?
Die rekursive Variante ist, wenn man die Berechnung einer einzelnen Fibonacci-Zahl betrachtet, in Θ(φn), wobei φ ≈ 1,618 der goldene Schnitt ist. Die Anzahl der rekursiven Funktionsaufrufe ist in der gleichen Komplexitätsklasse. Die iterativen und endrekursiven Varianten sind in Θ(n).
Allerdings: Da das Programm alle Fibonacci-Zahlen unterhalb einer Grenze ausgeben soll, ist es nicht notwendig, jede Fibonacci-Zahl wieder neu von vorne auszurechnen:
#include <iostream>
int main() {
unsigned long m, n;
m = 0;
n = 1;
while(m < 10000) {
std::cout << m << '\n';
unsigned long next = m + n;
m = n;
n = next;
}
}
...so ist die Berechnung der ersten n Fibonacci-Zahlen in Θ(n), mithin die Berechnung jeder einzelnen Zahl in Θ(1). Die gesamte Aufgabenstellung fällt entsprechend mit dem rekursiven Ansatz in Θ(φn) (geometrische Reihe) und mit dem iterativen in Θ(n2).
Komplexitätstechnisch geht es nicht mehr schneller. Man kann die Berechnung in die Compilezeit verlegen, wenn man lustig ist und die Obergrenze zur Compilezeit feststeht, aber da man immer noch n Zahlen ausgeben muss, ist das Ergebnis immer noch in Θ(n).
