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

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 > 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>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>0</math>
und ebenfalls für ein <math> c </math> mit <math> 0 < c < 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 > 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 > 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 > 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 < \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 > 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</math> Widerspruch!
Es existiert kein <math>\varepsilon> 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 < \alpha_i < 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) < 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}</math>

Literatur