Verständnisproblem Mastertheorem

Neue Frage »

Auf diesen Beitrag antworten »
MaRiee Verständnisproblem Mastertheorem

Meine Frage:
Hallo,

ich habe folgende Aufgabe zu lösen:

Gegeben ist die folgende Rekursionsgleichung T:

T(n) = 3n² (n/log 2(8)) + 16T (n/2)

Bestimme jeweils eine exakte Schranke für das Verhalten von T. In dem Fall, in denen das Master-Theorem anwendbar ist, beschreibe dessen Anwendung zum Finden von f.

Dazu habe ich folgende Fragen:
(1) was ist eine Rekursionsgleichung
(2) Wie bestimme ich exakt die Schranke
(3) mir ist immer noch die Bedeutung bzw. Interpretation vom Mastertheorem unschlüssig
(4) Wann ist es nicht anwendbar

Meine Ideen:
Das Mastertheorem ist definiert als T(n) = aT (a/b) + f(n).
a... Anzahl der Teilprombleme
b... Faktor, um welchen das Problem verringert wird

Mir fehlt komplett der Ansatz :-(
 
Auf diesen Beitrag antworten »
Karlito

Hallo MaRiee,

hier ein paar infos, die vielleicht weiter helfen. Da der Stoff schon einige Zeit her ist und ich mich noch nicht wieder vollständig eingelesen habe, bitte alles kritisch hinterfragen.

(1) Eine Rekursionsgleichung ist eine, die sich selbst wieder referenziert. Hier zum Beispiel hängt T(n) wiederum vom T(n) ab, da T(n) = ... + 16T(n/2)
(2) Daraus ergibt sich die exakte Bestimmung der Komplexität, indem du 16T(n/2) "expandierst". D.h. du wendest die Definition von T auf n/2 an und rechnest das Ergebnis aus.

Am Beispiel:
[latex]<br />
T(n) & = & 3n^2 (\frac{n}{log_28}) + 16T (\frac{n}{2}) <br />
& = & 3n^2 (\frac{n}{3}) + 16T (\frac{n}{2}) <br />
& = & n^2 \cdot n + 16T (\frac{n}{2}) <br />
& = & n^3 + 16T (\frac{n}{2}) <br />
& = & n^3 + 16\left(\left(\frac{n}{2}\right)^3 + 16T\left(\frac{\frac{n}{2}}{2}\right)\right)<br />
& = & n^3 + 16\left(\frac{n^3}{8} + 16T\left(\frac{n}{4}\right)\right)<br />
& = & n^3 + 2n^3 + 16^2T\left(\frac{n}{4}\right)<br />
& = & 3n^3 + 16^2T\left(\frac{n}{4}\right) \quad \dots \quad  T \text{ weiter expandieren und auf k "Expansionen" verallgemeinern}<br />
[/latex]

Da wir mit jedem Rekursionsschritt unsere Problemgröße halbieren müsste k maximal log2(n) groß sein. Damit können wir, so nehme ich momentan an, die obige Formel so verallgemeinern, dass wir die Komplexität in Abhängigkeit von n abschätzen können.

(3) Das Mastertheorem ist, soweit ich michr recht erinnere, nur eine Abkürzung. D.h. wir brauchen uns, wenn wir einen zutreffenden Fall für das Mastertheorem finden, die obige "expansion" nicht machen um die Laufzeit abzuschätzen, sondern können einfach nur das Mastertheorem anwenden und bekommen unsere Laufzeit. In die Details habe ich leider nicht geschaut.

(4) Kann ich leider aktuell nicht beantworten.

Besten Gruß,

Karlito
 
Neue Frage »
Antworten »


Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »