0 Daumen
71 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¨at des Algorithmus RekAlg5.


Unbenannt.JPG

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

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.

von 3,5 k

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Stacklounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community