0 Daumen
789 Aufrufe

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.

Avatar von

Der Algorithmus hat einen Fehler. Im Falle von \(n=0\) - und das passiert unweigerlich - läuft er in eine Endlosschleife. Also muss \(n \le 1\) noch extra behandelt werden.

1 Antwort

0 Daumen

Die Zeilen 16 bis 19 haben eine Komplexität von n³.

Die Zeilen 20 bis 22 teilen das Problem in 3 Teilprobleme auf, von denen jedes halb so groß ist wie das ursprüngliche.

T(n) = 3T(n/2) + n³

Master-Theorem.

Avatar von 5,7 k

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Stacklounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community