Master Theorem

Master Theorem

Der Begriff 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.

Inhaltsverzeichnis

Allgemeine Form

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 ≥ 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) die durch die Division des Problems und der Kombination der Teillösungen entstehen

Weiterhin benötigt man für die Benutzung des Master-Theorems noch den Logarithmus von a zur Basis b (logba), welchen man aus den beiden Größen a und b errechnen kann.

Das Master-Theorem unterscheidet sich in 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 \hbox{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 hinreichend große 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_b(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) = 1000n2
  logba = log28 = 3
  a = 2, b = 2
  f(n) = 10n
  logba = log22 = 1
  a = 2, b = 2
  f(n) = n2
  logba = log22 = 1
1. Bedingung: f(n) \in \hbox{O}\left( n^{\log_b a - \varepsilon} \right) 
für ein \varepsilon &amp;gt; 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 &amp;gt; 0
Werte einsetzen: 1000n^2 \in \hbox{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 &amp;gt; 0: 1000n^2 \in \hbox{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

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) = n3ln(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 &amp;lt; \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 &amp;gt; 0 : 0 &amp;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 Widerspruch!
Es existiert kein \varepsilon&amp;gt; 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 notwendige 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

  • Angenommen es ist folgende Rekurrenz gegeben, die sich mit der zusätzlichen Konstante c von der allgemeinen Form unterscheidet.
T(n) = a T(\textstyle \frac{n}{b}+c) + f(n)
Wenn n hinreichend groß gewählt wird, fällt die Konstante c nicht ins Gewicht. Aus diesem Grund kann man solche Rekurrenzen so behandeln, als wäre c = 0.
  • 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 als \tfrac{n}{b} interpretieren.
  • 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_b(n)= \textstyle \frac{\log_a(n)}{\log_a(b)} = c\sdot \log_a{n} \in \Theta( \log_a{n}) = \Theta( \lg{n})

Allgemeinere Form

In allgemeinerer Form gilt auch

Definition

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 &amp;lt; \alpha_i &amp;lt; 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) &amp;amp; \mbox{falls } \sum_{i=1}^{m}(\alpha_i^k) &amp;lt; 1 \\
\Theta(n^k \log n) &amp;amp; \mbox{falls } \sum_{i=1}^{m}(\alpha_i^k) = 1 \\
\Theta(n^c) \mbox{ mit } \sum_{i=1}^{m}(\alpha_i^c) = 1 &amp;amp; \mbox{falls } \sum_{i=1}^{m}(\alpha_i^k) &amp;gt; 1
\end{cases}

Literatur

  • Th.H.Cormen/C.E.Leiserson/R.Rivest/C.Stein: Algorithmen - Eine Einführung. Oldenbourg Verlag 2004. ISBN 3-486-27515-1
  • Th.E.Cormen/C.E.Leiserson/R.Rivest/C.Stein: Introduction to Algorithms. MIT Press 2002 ISBN 0-262-03293-7

Siehe auch


Wikimedia Foundation.

Игры ⚽ Нужна курсовая?

Schlagen Sie auch in anderen Wörterbüchern nach:

  • Master theorem — For a result in enumerative combinatorics, see MacMahon Master theorem. In the analysis of algorithms, the master theorem provides a cookbook solution in asymptotic terms (using Big O notation) for recurrence relations of types that occur in the… …   Wikipedia

  • Master-Theorem — Der Begriff 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 …   Deutsch Wikipedia

  • Master-Method — Der Begriff 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 …   Deutsch Wikipedia

  • Master Method — Der Begriff 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 …   Deutsch Wikipedia

  • Master of Financial Economics — A master’s degree in financial economics provides an understanding of theoretical finance and the underlying economic framework.[1] The degree is postgraduate, and may incorporate a thesis or research component. Programs are often a joint… …   Wikipedia

  • Master equation — See Lindblad equation for the master equation used in quantum physics See also Batalin–Vilkovisky formalism for the classical and quantum master equations in quantum field theory. In physics and chemistry and related fields, master equations are… …   Wikipedia

  • McNaughton's Theorem — In automata theory, McNaughton s theorem refers to a theorem that asserts that the set of ω regular languages is identical to the set of languages recognizable by deterministic Muller automata. [1] This theorem is proven by supplying an algorithm …   Wikipedia

  • Four color theorem — Example of a four colored map A four colori …   Wikipedia

  • Liouville's theorem (complex analysis) — In complex analysis, Liouville s theorem, named after Joseph Liouville, states that every bounded entire function must be constant. That is, every holomorphic function f for which there exists a positive number M such that | f ( z )| ≤ M for all… …   Wikipedia

  • Akra-Bazzi-Theorem — In der Informatik dient das Akra Bazzi Theorem, oder auch die Akra Bazzi Methode, dazu, das asymptotische Verhalten von Lösungen mathematischer Rekursionsgleichungen zu bestimmen, die bei der asymptotischen Analyse insbesondere von Divide and… …   Deutsch Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”