Informatiker Board | Druckvorschau: Verständnisproblem Mastertheorem

Informatiker Board (http://www.informatikerboard.de/board/index.php)
- Themengebiete (http://www.informatikerboard.de/board/board.php?boardid=1)
--- Praktische Informatik (http://www.informatikerboard.de/board/board.php?boardid=6)
---- Algorithmen (http://www.informatikerboard.de/board/board.php?boardid=17)
----- Verständnisproblem Mastertheorem (http://www.informatikerboard.de/board/thread.php?threadid=3732)

Geschrieben von MaRiee am 17.10.2017 um 22:18:

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 :-(

Geschrieben von Karlito am 18.10.2017 um 17:02:

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] T(n) & = & 3n^2 (\frac{n}{log_28}) + 16T (\frac{n}{2}) & = & 3n^2 (\frac{n}{3}) + 16T (\frac{n}{2}) & = & n^2 \cdot n + 16T (\frac{n}{2}) & = & n^3 + 16T (\frac{n}{2}) & = & n^3 + 16\left(\left(\frac{n}{2}\right)^3 + 16T\left(\frac{\frac{n}{2}}{2}\right)\right) & = & n^3 + 16\left(\frac{n^3}{8} + 16T\left(\frac{n}{4}\right)\right) & = & n^3 + 2n^3 + 16^2T\left(\frac{n}{4}\right) & = & 3n^3 + 16^2T\left(\frac{n}{4}\right) \quad \dots \quad T \text{ weiter expandieren und auf k "Expansionen" verallgemeinern} [/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