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;
}
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;
}