Frage:
Vom Algorithmus zu einer Rekursionsgleichung
a) Stellen Sie die Rekursionsgleichung zur Bestimmung der Zeitkomplexität des Algorithmus RekAlg5 in Abhängigkeit von der Eingabegröße auf und geben Sie an, welches die für die Zeitkomplexität relevante Eingabegröße ist. (Vernachlässigen Sie dabei die Gaussklammern.)
b) Bestimmen Sie die Zeitkomplexität des Algorithmus RekAlg5.
Der folgende rekursive Algorithmus berechnet eine Funktion \( g: \mathbb{N}^{2} \rightarrow \mathbb{N} \).
Nehmen Sie an, dass \( f: \mathbb{N}^{3} \rightarrow \mathbb{N} \in \Theta(1) \).
Algorithmus 1.2 (RekAlg5)
Eingabe: start, end \( \in \mathbb{N} \)
Ausgabe: \( z \)
REKALG5( start, end \( ) \)
\( n \leftarrow e n d- \) start
\( z \leftarrow n \)
if \( n=1 \) then
do return \( z \)
for \( k \leftarrow n \) downto 1 do
for \( j \leftarrow 1 \) to \( n \) do
for \( l \leftarrow 1 \) to \( n \) do
\( z \leftarrow z+f(k, j, l) \)
\( z \leftarrow z+\operatorname{REKALG} 5(1,\lfloor n / 2\rfloor) \)
\( z \leftarrow z+\operatorname{REKALG5}(\lfloor n / 4\rfloor,\lfloor 3 n / 4\rfloor) \)
\( z \leftarrow z+\operatorname{REKALG5}(\lfloor n / 2\rfloor, n) \)
return \( z \)
Ansatz/Problem:
Ich verstehe den Algorithmus leider nicht ganz deswegen ist das alles nur eine Vermutung, also
T(n) = { 1 , falls n=1
T(1)+ T(n/2) , falls n ≤ k ≤ 1
T(n/4)+T(3n/4), falls 1≤ j ≤ n
T(n/2)+T(n), falls falls 1≤ l ≤ n
Ich bin mir auch nicht sicher ob ich da überhaupt den richtigen ansatz habe, es gibt da ja noch die möglichkeit mit dem Master Theorem.
