Mastertheorem?
Hey,
Ich verstehe leider nicht, wie ich dies lösen soll trotz dieser "Anleitung"... könnte mir jemand das vllt am Beispiel von a. erklären?
Wäre wirklich super lieb.:)
2 Antworten
Obwohl ich keine theoretische Informatik studiert habe und mir daher das o.g. Theorem nicht bekannt ist, scheint die Aufgabe eine reine Einsetz-Übung zu sein. In (a) gilt:
g(n) = 1.000*n^2 = O(n^2), also k = 2, weiter
a = 8 > b^k = 2^2 = 4,
also ist der dritte Teil des Theorems anzuwenden:
T(n) = O(n^(log_2(8))) = O(n^(log_2(2^3))) = O(n^3)
Der Satz, so wie er auf der Folie steht:
a)
Das Mastertheorem kann man anwenden um die Laufzeit eines Algorithmus zu bestimmen, der die Eingabe erst in kleinere Teile zerlegt, dann die Teilprobleme bearbeitet und dann die Teile zu einer gesamten Lösung zusammensetzt ("Teile-und-Herrsche").
- T(n) ist die Laufzeit für die gesamte Eingabe
- b ist die Anzahl der Teilprobleme
- T(n/b) ist die benötigte Zeit um ein Teilproblem zu lösen, a zu lösende Teilprobleme => aT(n/b)
- g(n) ist die benötigte Zeit, um die gelösten Teilprobleme zusammenzusetzen
Hier sind es a = 8 zu lösende Probleme, b = 2 Teilprobleme, und die Laufzeit zum Kombinieren ist 1000n^2.
also ist k = 2.
Dann haben wir a = 8 > b^k = 2^2 = 4, also trifft hier der 3. Fall zu.
Jetzt musst Du nur einsetzen:
Hier ist noch ein Beispiel für einen echten Algorithmus bei dessen Analyse man das Mastertheorem anwenden kann:
1 = O(1) = O(n^0), also ist k = 0, a = 1 und somit trifft der 2. Fall zu, ergo ist O(log n) die Komplexität.
Ah Dankeschön! Eine Frage zu f. Dort ist k=0 oder? Weil es dort ja nur die 1 gibt