Der Hauptsatz der Laufzeitfunktionen – oder oft auch aus dem Englischen als Master-Theorem entlehnt – ist ein Spezialfall des Akra-Bazzi-Theorems und bietet eine schnelle Lösung für die Frage, in welcher Laufzeitklasse eine gegebene rekursiv definierte 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ätsklasse der Funktion anderweitig berechnen.
Das Master-Theorem bietet unter bestimmten Bedingungen asymptotische Abschätzungen für Lösungen der Rekursionsgleichung
Hierbei steht
für die gesuchte Laufzeitfunktion, während
und
Konstanten sind. Ferner bezeichnet
eine von
unabhängige und nicht negative Funktion. Damit das Master-Theorem angewendet werden kann, müssen für die beiden Konstanten die Bedingungen
und
erfüllt sein.
Interpretation der Rekursion für
:
= Anzahl der Unterprobleme in der Rekursion
= Teil des Originalproblems, welches wiederum durch alle Unterprobleme repräsentiert wird
= 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 |
| für ein | | für ein | und ebenfalls für ein mit und alle hinreichend großen gilt: | | |
Dann folgt: | | | |
Beispiel | | | |
Aus der Formel ist folgendes abzulesen: | , | | | | , | | | | , | | | |
1. Bedingung: | für ein | | für ein |
Werte einsetzen: | | | |
Wähle : | mit ✔ | ✔ | mit ✔ |
2. Bedingung: (nur im 3. Fall) | | | | Setze auch hier obige Werte ein: | ![{\displaystyle 2(\textstyle {\frac {n}{2}})^{2}\leq cn^{2}\Leftrightarrow }](https://wikimedia.org/api/rest_v1/media/math/render/svg/6eaf7d4d12ad2e63e6b57c722fb56ef04737108f) | Wähle c = ½: | ✔ | |
Damit gilt für die Laufzeitfunktion: | | | |
( ✔ = 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.
.
Auf den ersten Blick scheint es, dass der 3. Fall anzuwenden ist:
, ![{\displaystyle f(n)=n^{3}\ln(n)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/cb26e3b45c8f1deb6a6d78a2b85fc138be283fa0)
- Für den 3. Fall ist zu zeigen:
![{\displaystyle f(n)\in \Omega \left(n^{\log _{b}a+\varepsilon }\right)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/cdf990669cee3354e2726f5ae416a7bc2cf23af7)
- Definition vom Ω-Kalkül:
![{\displaystyle f(n)\in \Omega (g(n)):0<\liminf _{n\to \infty }\left|\textstyle {\frac {f(n)}{g(n)}}\right|\leq \infty }](https://wikimedia.org/api/rest_v1/media/math/render/svg/c2f42d30b96d128b276fa75ef421ec78b45f5d13)
- Angewandt auf
:
Widerspruch! - Es existiert kein
, so dass der Limes ungleich Null ist. Also ist der 3. Fall nicht auf diese Rekursionsgleichung anwendbar!
Es gilt:
, falls
Genau betrachtet stellt diese Formel eine Verallgemeinerung des zweiten Falls dar.
Lösung nach obiger Formel:
✔ - Da
die hinreichende Bedingung erfüllt, gilt nun: ![{\displaystyle T(n)=\Theta \left(n^{3}\ln ^{2}n\right)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/83cef331e18ecf8f6c44592a83fdf4f77866fa39)
- Siehe zu demselben Beispiel auch die Aufwandsabschätzung im Ο-Kalkül mit Hilfe der Substitutionsmethode.
Bemerkungen
- Angenommen, es ist folgende Rekurrenz gegeben, bei der
durch die Floor- oder Ceiling-Funktion angegeben werden:
- z. B.:
![{\displaystyle T(n)=aT(\lfloor {\tfrac {n}{b}}\rfloor )+f(n)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/26d0e03f0dfd79fa75ca6a4ecef5594158c56953)
- In diesem Fall kann man
oder auch
mit Hilfe der Form
abschätzen.
- Ob man nun
(Logarithmus naturalis) schreibt, oder
(dekadischer Logarithmus) ist egal, da nach den Logarithmengesetzen gilt:
![{\displaystyle \ln(n)=\log _{e}(n)=\textstyle {\frac {\log _{10}(n)}{\log _{10}(e)}}=c\cdot \log _{10}{n}\in \Theta (\log _{10}{n})=\Theta (\lg {n})}](https://wikimedia.org/api/rest_v1/media/math/render/svg/d4ad0fdc241fc2c63345b0376fe2df5e18bbc93f)
In allgemeinerer Form gilt auch:
Definition
Sei
die zu untersuchende Abbildung der Form
,
wobei
,
und
mit
.
wird hierfür implizit durch
oder
für
auf die reellen Zahlen fortgesetzt.
Dann gilt:
![{\displaystyle 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}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/d2268cc7b6640a483755cd5b255a2f1fca2b97e2)
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:
![{\displaystyle T(n)=2\cdot T(\textstyle {\frac {n}{2}})+c\cdot n.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/2aabb8611b6537a9f0d2cdbb87a0acf781ed39f5)
Wähle
,
und
.
Es folgt
Nach dem Master-Theorem folgt, dass Mergesort folgende Laufzeit besitzt:
![{\displaystyle T(n)\in \Theta (n\cdot \log(n))}](https://wikimedia.org/api/rest_v1/media/math/render/svg/0842af1149a2561f79b027a2c2b8a173f2ef7912)
Literatur
- Thomas H Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein: Algorithmen – eine Einführung. Oldenbourg, München / Wien 2004, ISBN 3-486-27515-1 (englisch: Introduction to algorithms. Übersetzt von Karen Lippert, Micaela Krieger-Hauwede).
- Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein: Introduction to Algorithms. 2. Auflage. MIT Press, Cambridge MA 2001, ISBN 0-262-03293-7.