Master-Theorem

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche

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[Bearbeiten]

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

T(n) = a \sdot T(\textstyle \frac{n}{b}) + f(n)

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

Interpretation der Rekurrenz T(n):

a   = Anzahl der Unterprobleme in der Rekursion
1/b = Teil des Originalproblems, welches wiederum durch alle Unterprobleme repräsentiert wird
f(n) = 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:
f(n) \in \mathcal{O}\left( n^{\log_b a - \varepsilon} \right) 
für ein \varepsilon>0
f(n) \in \Theta\left( n^{\log_b a} \right)
f(n) \in \Omega\left( n^{\log_b a + \varepsilon} \right) für ein \varepsilon>0
und ebenfalls für ein  c mit  0 < c < 1 und alle hinreichend großen n gilt:
a f( \textstyle \frac{n}{b} ) \le c f(n)
Dann folgt: T(n) \in \Theta\left( n^{\log_b a} \right) T(n) \in \Theta\left( n^{\log_b a} \log(n)\right) T(n) \in \Theta(f(n))
Beispiel T(n) = 8 T(\textstyle \frac{n}{2}) + 1000n^2 T(n) = 2 T(\textstyle \frac{n}{2}) + 10n T(n) = 2 T(\textstyle \frac{n}{2}) + n^2
Aus der Formel ist folgendes abzulesen:
  a = 8, b = 2
  f(n) = 1000n^2
  \log_b a = \log_2 8 = 3
  a = 2, b = 2
  f(n) = 10n
  \log_b a = \log_2 2 = 1
  a = 2, b = 2
  f(n) = n^2
  \log_b a = \log_2 2 = 1
1. Bedingung: f(n) \in \mathcal{O}\left( n^{\log_b a - \varepsilon} \right) 
für ein \varepsilon > 0
f(n) \in \Theta\left( n^{\log_b a} \right) f(n) \in \Omega\left( n^{\log_b a + \varepsilon} \right) für ein \varepsilon > 0
Werte einsetzen: 1000n^2 \in \mathcal{O}\left( n^{3 - \varepsilon} \right) 10n \in \Theta\left( n^{1} \right) n^2 \in \Omega\left( n^{1 + \varepsilon} \right)
Wähle  \varepsilon > 0: 1000n^2 \in \mathcal{O}\left( n^{2}\right) mit  \varepsilon = 1   10n \in \Theta\left( n \right)   n^2 \in \Omega\left( n^2 \right) mit  \varepsilon=1  
2. Bedingung: (nur im 3. Fall)
a f(\textstyle \frac{n}{b} ) \le c f(n)
Setze auch hier obige Werte ein:
2 (\textstyle \frac{n}{2} )^2 \le c n^2 \Leftrightarrow \textstyle \frac{1}{2} n^2 \le cn^2
Wähle c = ½:
 \forall n \ge 1 : \textstyle \frac{1}{2} n^2 \le \textstyle \frac{1}{2} n^2   
Damit gilt für die Laufzeitfunktion: T(n) \in \Theta( n^{3} ) T(n) \in \Theta( n \log(n)) T(n) \in \Theta(n^2)

= Wahre Aussage )

Verallgemeinerung des zweiten Falls[Bearbeiten]

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.

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

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

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

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

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

Lösung nach obiger Formel:

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)
Da f(n) die hinreichende Bedingung erfüllt, gilt nun: T(n) = \Theta\left( n^{3}\ln^{2}n \right)
Siehe zu demselben Beispiel auch die Aufwandsabschätzung im Ο-Kalkül mit Hilfe der Substitutionsmethode.

Bemerkungen[Bearbeiten]

  • Angenommen, es ist folgende Rekurrenz gegeben, bei der n/b durch die Floor- oder Ceiling-Funktion angegeben werden:
z. B.:  T(n) = a T( \lfloor \tfrac{n}{b} \rfloor ) + f(n)
In diesem Fall kann man \lfloor \tfrac{n}{b} \rfloor oder auch \lceil \tfrac{n}{b} \rceil mit Hilfe der Form \tfrac{n}{b} abschätzen.
  • Ob man nun  T(n) \in \Theta (\ln(n))  (Logarithmus naturalis) schreibt, oder  T(n) \in \Theta (\lg(n)) (dekadischer Logarithmus) ist egal, da nach den Logarithmengesetzen gilt:
\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})

Allgemeinere Form[Bearbeiten]

In allgemeinerer Form gilt auch:

Definition[Bearbeiten]

Sei T: \mathbb{N} \to \mathbb{N} die zu untersuchende Abbildung der Form

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

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

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

Dann gilt:

T(n) \in
\begin{cases} \Theta(n^k) & \mbox{falls } \sum_{i=1}^{m}(\alpha_i^k) < 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) > 1
\end{cases}

Literatur[Bearbeiten]