Wie ist die Komplexität dieser beiden Algorithmen bei gegebener Problemgröße n?



public static long recursiveFibonacci (int n) {
if(n==0)
return 0;
if(n==1)
return 1;

return
recursiveFibonacci (n-1) + recursiveFibonacci (n-2);
}

public static long iterativeFibonacci (int n) {
if(n==0) return 0;
if(n==1) return 1;

int k = n;
long tmp0 = 0;
long tmp1 = 1;
long erg = 0;

while (k > 1) {
erg = tmp0 +tmp1;
tmp0 = tmp1;
tmp1 = erg;
k = k - 1;
}
return erg;
}

Servus!

http://www.ph-ludwigsburg.de/mathema...inf1/folien/13

Gruß Tom

@Thomas Darimont
die Seite gibts nicht.

@PPhilipp
rekursive Sachen sind oft einfacher zu realisieren von Programmeirstil her, allerdings sind iterative Sachen meist schneller und auch Speicherplatzschonender da meist nicht diese vielen neuen Functionsaufrufe gespeichert werden müssen.

Für Fibonacci stellt sich die Frage nur theroetisch. Sobald ud nämlich was größeres als 15 eingibst, hast du ein rießen Problem. Und rekursiv muss nicht unbedingt langsammer sein. Es kommt auf die Sprache an. Wenn du das z.B. mit SML oder Haskel machst ist es ziemlich schnell.

Servus!

Hier der richtige Link:
http://www.ph-ludwigsburg.de/mathema...imperativ3.ppt

Gruß tom

rekursive Sachen sind oft einfacher zu realisieren von Programmeirstil her, allerdings sind iterative Sachen meist schneller und auch Speicherplatzschonender da meist nicht diese vielen neuen Functionsaufrufe gespeichert werden müssen.

Deswegen gibt es schlaue Compiler die Endrekursive Algorithmen in Iterationen umwandeln.