Master-Theorem - LinkFang.de





Master-Theorem


Der Hauptsatz der Laufzeitfunktionen oder oft englisch Master-Theorem, das ein Spezialfall des Akra-Bazzi-Theorems ist, bietet eine schnelle Lösung für die Frage, in welcher Laufzeitklasse eine gegebene rekursiv definierte Funktion liegt. Jedoch kann mit dem Master-Theorem nicht jede rekursiv definierte Funktion gelöst werden. Lässt sich keiner der drei möglichen Fälle des Master-Theorems auf die Funktion T anwenden, so muss man die Komplexitätsklasse der Funktion anderweitig berechnen.

Allgemeine Form

Die allgemeine Form für die Anwendung des Master-Theorems sieht wie folgt aus:

[math]T(n) = a \sdot T(\textstyle \frac{n}{b}) + f(n)[/math]

Hierbei steht [math]T(n)[/math] für die zu untersuchende Laufzeitfunktion, während [math]a[/math] und [math]b[/math] Konstanten sind. Ferner bezeichnet [math]f(n)[/math] eine von [math]T(n)[/math] unabhängige und nicht negative Funktion. Damit das Master-Theorem angewendet werden kann, muss für die beiden Konstanten die Bedingung [math]a \ge 1[/math] und [math]b \gt 1[/math] erfüllt sein.

Interpretation der Rekurrenz [math]T(n)[/math]:

[math]a[/math]   = Anzahl der Unterprobleme in der Rekursion
[math]1/b[/math] = Teil des Originalproblems, welches wiederum durch alle Unterprobleme repräsentiert wird
[math]f(n)[/math] = Kosten (Aufwand, Nebenkosten), die durch die Division des Problems und die Kombination der Teillösungen entstehen

Das Master-Theorem unterscheidet drei Fälle, wobei sich höchstens ein Fall auf die gegebene Rekursion anwenden lässt. Passt keiner der Fälle, so lässt sich das Master-Theorem nicht anwenden und man muss sich anderer Methoden bedienen.

Erster Fall Zweiter Fall Dritter Fall
Allgemein
Falls gilt:
[math]f(n) \in \mathcal{O}\left( n^{\log_b a - \varepsilon} \right)[/math] 
für ein [math]\varepsilon\gt0[/math]
[math]f(n) \in \Theta\left( n^{\log_b a} \right)[/math]
[math]f(n) \in \Omega\left( n^{\log_b a + \varepsilon} \right)[/math] für ein [math]\varepsilon\gt0[/math]
und ebenfalls für ein [math] c [/math] mit [math] 0 \lt c \lt 1[/math] und alle hinreichend großen [math]n[/math] gilt:
[math]a f( \textstyle \frac{n}{b} ) \le c f(n)[/math]
Dann folgt: [math]T(n) \in \Theta\left( n^{\log_b a} \right)[/math] [math]T(n) \in \Theta\left( n^{\log_b a} \log(n)\right)[/math] [math]T(n) \in \Theta(f(n))[/math]
Beispiel [math]T(n) = 8 T(\textstyle \frac{n}{2}) + 1000n^2[/math] [math]T(n) = 2 T(\textstyle \frac{n}{2}) + 10n[/math] [math]T(n) = 2 T(\textstyle \frac{n}{2}) + n^2[/math]
Aus der Formel ist folgendes abzulesen:
  [math]a = 8[/math], [math]b = 2[/math]
  [math]f(n) = 1000n^2[/math]
  [math]\log_b a = \log_2 8 = 3[/math]
  [math]a = 2[/math], [math]b = 2[/math]
  [math]f(n) = 10n[/math]
  [math]\log_b a = \log_2 2 = 1[/math]
  [math]a = 2[/math], [math]b = 2[/math]
  [math]f(n) = n^2[/math]
  [math]\log_b a = \log_2 2 = 1[/math]
1. Bedingung: [math]f(n) \in \mathcal{O}\left( n^{\log_b a - \varepsilon} \right)[/math] 
für ein [math]\varepsilon \gt 0[/math]
[math]f(n) \in \Theta\left( n^{\log_b a} \right)[/math] [math]f(n) \in \Omega\left( n^{\log_b a + \varepsilon} \right)[/math] für ein [math]\varepsilon \gt 0[/math]
Werte einsetzen: [math]1000n^2 \in \mathcal{O}\left( n^{3 - \varepsilon} \right)[/math] [math]10n \in \Theta\left( n^{1} \right)[/math] [math]n^2 \in \Omega\left( n^{1 + \varepsilon} \right)[/math]
Wähle [math] \varepsilon \gt 0[/math]: [math]1000n^2 \in \mathcal{O}\left( n^{2}\right)[/math] mit [math] \varepsilon = 1[/math]   [math]10n \in \Theta\left( n \right)[/math]   [math]n^2 \in \Omega\left( n^2 \right)[/math] mit [math] \varepsilon=1[/math]  
2. Bedingung: (nur im 3. Fall)
[math]a f(\textstyle \frac{n}{b} ) \le c f(n)[/math]
Setze auch hier obige Werte ein:
[math]2 (\textstyle \frac{n}{2} )^2 \le c n^2 \Leftrightarrow [/math][math]\textstyle \frac{1}{2} n^2 \le cn^2[/math]
Wähle c = ½:
[math] \forall n \ge 1 : \textstyle \frac{1}{2} n^2 \le \textstyle \frac{1}{2} n^2 [/math]  
Damit gilt für die Laufzeitfunktion: [math]T(n) \in \Theta( n^{3} )[/math] [math]T(n) \in \Theta( n \log(n))[/math] [math]T(n) \in \Theta(n^2)[/math]

= Wahre Aussage )

Verallgemeinerung des zweiten Falls

Nicht alle Rekurrenzgleichungen lassen sich mithilfe einer der drei Fällen des Mastertheorems lösen. So ist zum Beispiel die folgende Rekurrenzgleichung nicht direkt mit dem Mastertheorem lösbar.

[math]T(n) = 8 T( \textstyle \frac{n}{2}) + n^3\ln(n)[/math].

Auf den ersten Blick scheint es, dass der 3. Fall anzuwenden ist:

[math]a=8,[/math]  [math]b=2[/math],  [math]f(n)=n^3\ln(n)[/math]
Für den 3. Fall ist zu zeigen: [math]f(n) \in \Omega\left( n^{\log_b a + \varepsilon} \right)[/math]
Definition vom Ω-Kalkül:[math]f(n) \in \Omega(g(n)) : 0 \lt \liminf_{n \to \infty} \left|\textstyle \frac{f(n)}{g(n)}\right| \le \infty[/math]
Angewandt auf [math]n^3\ln(n) \in \Omega\left( n^{\log_2 8 + \varepsilon} \right)[/math]:
[math]\exists \varepsilon \gt 0 : 0 \lt \liminf_{n \to \infty} \left|\frac{f(n)}{g(n)}\right| = \liminf_{n \to \infty} \left| \frac{n^3\ln(n)}{n^{\log_2 8 + \varepsilon}}\right| = \liminf_{n \to \infty} \left| \frac{\ln(n)}{n^{\varepsilon}}\right| = 0 \Rightarrow[/math] Widerspruch!
Es existiert kein [math]\varepsilon\gt 0[/math], so dass der Limes ungleich Null ist. Also ist der 3. Fall nicht auf diese Rekursionsgleichung anwendbar!

Es gilt: [math]T(n) = \Theta\left( n^{\log_b a}\ln^{k+1}n \right)[/math], falls [math]f(n) \in \Theta\left( n^{\log_b a}\ln^{k}n \right)[/math]

Genau betrachtet stellt diese Formel eine Verallgemeinerung des zweiten Falls dar.

Lösung nach obiger Formel:

[math]f(n) = n^3\ln(n) \in \Theta\left( n^{\log_b a}\ln^{k}n \right) = \Theta\left( n^{\log_2 8}\ln^{1}n \right) = \Theta\left(n^{3}\ln(n) \right)[/math]
Da [math]f(n)[/math] die hinreichende Bedingung erfüllt, gilt nun: [math]T(n) = \Theta\left( n^{3}\ln^{2}n \right)[/math]
Siehe zu demselben Beispiel auch die Aufwandsabschätzung im Ο-Kalkül mit Hilfe der Substitutionsmethode.

Bemerkungen

  • Angenommen, es ist folgende Rekurrenz gegeben, bei der [math]n/b[/math] durch die Floor- oder Ceiling-Funktion angegeben werden:
z. B.:  [math]T(n) = a T( \lfloor \tfrac{n}{b} \rfloor ) + f(n)[/math]
In diesem Fall kann man [math]\lfloor \tfrac{n}{b} \rfloor[/math] oder auch [math]\lceil \tfrac{n}{b} \rceil[/math] mit Hilfe der Form [math]\tfrac{n}{b}[/math] abschätzen.
  • Ob man nun [math] T(n) \in \Theta (\ln(n))[/math]  (Logarithmus naturalis) schreibt, oder  [math]T(n) \in \Theta (\lg(n))[/math] (dekadischer Logarithmus) ist egal, da nach den Logarithmengesetzen gilt:
[math]\ln(n) = \log_e(n)= \textstyle \frac{\log_{10}(n)}{\log_{10}(e)} = c\sdot \log_{10}{n} \in \Theta( \log_{10}{n}) = \Theta( \lg{n})[/math]

Allgemeinere Form

In allgemeinerer Form gilt auch:

Definition

Sei [math]T: \mathbb{N} \to \mathbb{N}[/math] die zu untersuchende Abbildung der Form

[math]T(n) = \sum_{i=1}^{m} T\left(\alpha_i n\right) + f(n)[/math],

wobei [math]\alpha_i \in \mathbb{R}: 0 \lt \alpha_i \lt 1[/math], [math]m \in \mathbb{N}: m \ge 1[/math] und [math]f(n) \in \Theta(n^k)[/math] mit [math]k \in \mathbb{N}: k \ge 0[/math].

[math]T[/math] wird hierfür implizit durch [math]T(x) := T(\lfloor x \rfloor)[/math] oder [math]T(\lceil x \rceil)[/math] für [math]x \in \mathbb{R^+}[/math] auf die reellen Zahlen fortgesetzt.

Dann gilt:

[math]T(n) \in \begin{cases} \Theta(n^k) & \mbox{falls } \sum_{i=1}^{m}(\alpha_i^k) \lt 1 \\ \Theta(n^k \log n) & \mbox{falls } \sum_{i=1}^{m}(\alpha_i^k) = 1 \\ \Theta(n^c) \mbox{ mit } \sum_{i=1}^{m}(\alpha_i^c) = 1 & \mbox{falls } \sum_{i=1}^{m}(\alpha_i^k) \gt 1 \end{cases}[/math]

Literatur


Kategorien: Rekursion | Komplexitätstheorie

Quelle: Wikipedia - http://de.wikipedia.org/wiki/Master-Theorem (Vollständige Liste der Autoren des Textes [Versionsgeschichte])    Lizenz: CC-by-sa-3.0

Änderungen: Alle Bilder mit den meisten Bildunterschriften wurden entfernt. Ebenso alle zu nicht-existierenden Artikeln/Kategorien gehenden internen Wikipedia-Links (Bsp. Portal-Links, Redlinks, Bearbeiten-Links). Entfernung von Navigationsframes, Geo & Normdaten, Mediadateien, gesprochene Versionen, z.T. ID&Class-Namen, Style von Div-Containern, Metadaten, Vorlagen, wie lesenwerte Artikel. Ansonsten sind keine Inhaltsänderungen vorgenommen worden. Weiterhin kann es durch die maschinelle Bearbeitung des Inhalts zu Fehlern gerade in der Darstellung kommen. Darum würden wir jeden Besucher unserer Seite darum bitten uns diese Fehler über den Support mittels einer Nachricht mit Link zu melden. Vielen Dank!

Stand der Informationen: August 201& - Wichtiger Hinweis: Da die Inhalte maschinell von Wikipedia übernommen wurden, ist eine manuelle Überprüfung nicht möglich. Somit garantiert LinkFang.de nicht die Richtigkeit und Aktualität der übernommenen Inhalte. Sollten die Informationen mittlerweile fehlerhaft sein, bitten wir Sie darum uns per Support oder E-Mail zu kontaktieren. Wir werden uns dann innerhalb von spätestens 10 Tagen um Ihr Anliegen kümmern. Auch ohne Anliegen erfolgt mindestens alle drei Monate ein Update der gesamten Inhalte.