Fibonacci und Komplexität

P

PPhilipp

Grünschnabel
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;
}
 
hmm,

@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.
 
-

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.
Zum Vergrößern anklicken....
Deswegen gibt es schlaue Compiler die Endrekursive Algorithmen in Iterationen umwandeln. :)
 
Um antworten zu können musst du eingeloggt sein.

Neue Beiträge

Zurück