 Verständnisproblem Mastertheorem |
MaRiee
Grünschnabel
Dabei seit: 17.10.2017
Beiträge: 1
 |
|
| 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 :-(
|
|
17.10.2017 22:18 |
|
|
Karlito 
Kaiser
Dabei seit: 11.04.2011
Beiträge: 1.461
|
|
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]](http://www.matheboard.de/latex2png/latex2png.php?<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 />
)
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
|
|
|
18.10.2017 17:02 |
|
|
|
