imported>UspJunkie: /* growthexperiments-addlink-summary-summary:1|0|0 */

2025-08-26T08:10:05Z

growthexperiments-addlink-summary-summary:1|0|0

Neue Seite

Der '''Hauptsatz der Laufzeitfunktionen''' – oder oft auch aus dem Englischen als '''Master-Theorem''' entlehnt – ist ein Spezialfall des [[Akra-Bazzi-Theorem]]s und bietet eine schnelle Lösung für die Frage, in welcher [[Laufzeitklasse]] eine gegebene [[Rekursion|rekursiv]] definierte [[Funktion (Programmierung)|Funktion]] liegt. Mit dem Master-Theorem kann allerdings 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ät (Informatik)|Komplexitätsklasse]] der Funktion anderweitig berechnen.

== Allgemeine Form ==

Das Master-Theorem bietet unter bestimmten Bedingungen [[Zeitkomplexität|asymptotische Abschätzungen]] für Lösungen der [[Rekursionsgleichung]]

<math>T(n) = a \sdot T(\textstyle \frac{n}{b}) + f(n).</math>

Hierbei steht <math>T(n)</math> für die gesuchte 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, müssen für die beiden Konstanten die Bedingungen <math>a \ge 1</math> und <math>b > 1</math> erfüllt sein.

Interpretation der Rekursion für <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.

{| class="wikitable"

! style="width:90px;"|
!Erster Fall
!Zweiter Fall
!Dritter Fall
|-style="vertical-align:top;"
|bgcolor="#D4E7F8"|
{|border="0" cellspacing="0" cellpadding="0"
|- style="background-color:#D4E7F8;"
!Allgemein
|- style="background-color:#D4E7F8;"
|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>
|
{|border="0" cellspacing="0" cellpadding="3"
|<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>
|}
|-
|bgcolor="#AACDEF"|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>
|-
! style="text-align:left;"|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>
|-
|bgcolor="#DCFADC"|Aus der Formel ist folgendes abzulesen:
|
{|border="0" cellspacing="0" cellpadding="0"
|  <math>a = 8</math>, <math>b = 2</math>
|-
|  <math>f(n) = 1000n^2</math>
|-
|  <math>\log_b a = \log_2 8 = 3</math>
|}
|
{|border="0" cellspacing="0" cellpadding="0"
|  <math>a = 2</math>, <math>b = 2</math>
|-
|  <math>f(n) = 10n</math>
|-
|  <math>\log_b a = \log_2 2 = 1</math>
|}
|
{|border="0" cellspacing="0" cellpadding="0"
|  <math>a = 2</math>, <math>b = 2</math>
|-
|  <math>f(n) = n^2</math>
|-
|  <math>\log_b a = \log_2 2 = 1</math>
|}
|-
|bgcolor="#DCFADC"|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>
|-
|bgcolor="#DCFADC" width="105" |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>
|-
|bgcolor="#DCFADC"|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>  ✔
|-
|bgcolor="#DCFADC" valign="top" width="108"|2. Bedingung: (nur im 3. Fall)
|
|
|
{|border="0" cellspacing="0" cellpadding="3"
|<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>  ✔
|}
|-
|bgcolor="#ADEDAD"|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 [[Landau-Symbole#Definition|Ω-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) \in \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-Funktion|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 [[Logarithmus|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_0} \to \mathbb{N_0}</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_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^+_0}</math> auf die [[Reelle Zahl|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>

== Beispiel==

===Mergesort===

Als Beispiel für die Berechnung der Laufzeit eines rekursiven Algorithmus mit Hilfe des Master-Theorem betrachten wir das rekursive [[Sortierverfahren]] [[Mergesort]].

[[Mergesort]] besitzt folgende Rekursionsgleichung:

:<math>T(n) = 2 \sdot T(\textstyle \frac{n}{2}) + c \sdot n.</math>

Wähle <math> a = 2 </math>, <math> b = 2 </math> und <math> f(n) = c \sdot n </math>.

Es folgt <math>\log_b a = \log_2 2 = 1</math>

Nach dem Master-Theorem folgt, dass [[Mergesort]] folgende Laufzeit besitzt:

:<math>T(n) \in \Theta (n \sdot \log (n))</math>

== Literatur ==
* {{BibISBN|3486275151}}
* {{BibISBN|0262032937}}

[[Kategorie:Rekursion]]
[[Kategorie:Komplexitätstheorie]]

Master-Theorem - Versionsgeschichte

imported>UspJunkie: /* growthexperiments-addlink-summary-summary:1|0|0 */