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¨at des Algorithmus RekAlg5.
Text erkannt:
Der folgende rekursive Algorithmus bercchnct ci-
ne 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)
\( 12 \quad n \leftarrow \) end \( - \) start
\( 13 \quad z \leftarrow n \)
14 if \( n=1 \) then
\( 15 \quad \) do return \( z \)
16 for \( k \leftarrow n \) downto 1 do
17 for \( j \leftarrow 1 \) to \( n \) do
\( 18 \quad \) for \( l \leftarrow 1 \) to \( n \) do
\( 19 \quad z \leftarrow z+f(k, j, l) \)
\( 20 \quad z \leftarrow z+ \) REKALG \( 5(1,\lfloor n / 2\rfloor) \)
\( 21 \quad z \leftarrow z+ \) REKALG \( 5(\lfloor n / 4\rfloor,\lfloor 3 n / 4\rfloor) \)
\( 22 \quad z \leftarrow z+ \) REKALG \( 5(\lfloor n / 2\rfloor, n) \)
23 return \( z \)
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 aber da weiß ich nicht wie ich von den 3 zu einer gleichung komme
