Vom Algorithmus zur Rekursionsgleichung |
| 18.10.2019, 12:25 | Auf diesen Beitrag antworten » |
| Miakosa | Vom Algorithmus zur Rekursionsgleichung 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. |
|
|
|
|
|
Verwandte Themen
| Die Beliebtesten » |
| Die Größten » |
|
| Die Neuesten » |
|
