Frage zur Rekursion

mucos001

Mitglied
1 für n=1
f(n-1)*f(n-1) +1 für n>1


a)Programmieren Sie die Funktion f rekursiv in Java, so dass Sie eine Zeitkomplexität von O(2n) und eine Rekursionstiefe von O(n) besitzt.

public static int fRekursiv1(int n)
{
assert(n>=1);

if(n==1)
{
return 1;
}
else
{
return fRekursiv1(n-1)*fRekursiv1(n-1)+1;
}
}

b)Programmieren Sie die Funktion f rekursiv in Java, so dass Sie eine Zeitkomplexität von O(n) und eine Rekursionstiefe von O(n) besitzt.




c)Programmieren Sie die Funktion f iterativ in Java, so dass Sie eine Zeitkomplexität von O(n) besitzt.
Hinweis: Funktionen der Klasse Math dürfen nicht benutzt werden




Hallo Forum
Nun hab ich die Aufgabe a gelöst.Weiß ich nicht Aufgabe b und c
Könntet Ihr mir bitte helfen?
danke
 

LimDul

Top Contributor
Deine Aufgabenstellung stimmt nicht.

O(2n) ist das gleiche wie O(n).

Und deine Lösung in a) hat nicht O(2n) sondern O(n²) als Zeitkomplexität.
 

Neue Themen


Oben