|
|
Meine Frage:
Aufgabe:
Eingabe = n ? N (Natürliche Zahlen)
Ausgabe = keine
Algorithmus LINALG nicht rekursiv,liefert einen Wert vom Typ boolean und hat eine lineare Zeitkopmplexität
REKALG(n)
1 if n=1
2 then return
3 if LINALG(n)
4 then REKALG (?2n/3?)
5 else REKLAG(?n/3?)
a) Stellen Sie die Rekursionsgleichung zur Bestimmung der maximaleen Anzahl der rekursiven Auftrufe dieses Algorithmus mit dem Argument n auf. Zählen Sie die Auswertung der Anfangsbedinung auch als einen rekursiven Aufruf. ( Auf und Abrunden in der rekursionsgleichung vernachlässigen)
b) Lösen Sie die Rekursionsgleichung mit dem Master Theorems.
Meine Ideen:
mein Lösungsweg für a:
Ich habe erstmal für n ein paar werte eingesetzt:
n=1
Alg. beendet
n=2
LINALG (n)
then = 1
Alg. beendet
n=3
LINALG(3)
=2
Da n=2 und LINALG (3)
else = 1
Alg. beendet.
Ich bin mir nur jetzt unsicher ob ich den algorithmus so richtig verstanden habe und wie genau ich dadurch jetzt zur rekursionsgleichung komme.
|
|
