Frage zur Rekursion

Diskutiere Frage zur Rekursion im Hausaufgaben Bereich.
M

mucos001

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
 
L

LimDul

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

Meniskusschaden

Weiß ich nicht Aufgabe b
Jeder Aufruf von fRekursiv1() zieht zwei weitere Aufrufe nach sich. Mit jeder Rekursionsebene verdoppelt sich also die Anzahl der Aufrufe. Wie könntest du die Formel denn verändern, damit nicht mehr zwei, sondern nur noch ein Aufruf nötig ist?
 
Thema: 

Frage zur Rekursion

Passende Stellenanzeigen aus deiner Region:
Anzeige

Neue Themen

Anzeige

Anzeige
Oben