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 Losung fur die Frage in welcher Laufzeitklasse eine gegebene rekursiv definierte Funktion liegt Mit dem Master Theorem kann allerdings nicht jede rekursiv definierte Funktion gelost werden Lasst sich keiner der drei moglichen Falle des Master Theorems auf die Funktion T anwenden so muss man die Komplexitatsklasse der Funktion anderweitig berechnen Inhaltsverzeichnis 1 Allgemeine Form 2 Verallgemeinerung des zweiten Falls 3 Bemerkungen 4 Allgemeinere Form 4 1 Definition 5 Beispiel 5 1 Mergesort 6 LiteraturAllgemeine Form BearbeitenDas Master Theorem bietet unter bestimmten Bedingungen asymptotische Abschatzungen fur Losungen der RekursionsgleichungT n a T n b f n displaystyle T n a cdot T textstyle frac n b f n nbsp Hierbei steht T n displaystyle T n nbsp fur die gesuchte Laufzeitfunktion wahrend a displaystyle a nbsp und b displaystyle b nbsp Konstanten sind Ferner bezeichnet f n displaystyle f n nbsp eine von T n displaystyle T n nbsp unabhangige und nicht negative Funktion Damit das Master Theorem angewendet werden kann mussen fur die beiden Konstanten die Bedingungen a 1 displaystyle a geq 1 nbsp und b gt 1 displaystyle b gt 1 nbsp erfullt sein Interpretation der Rekursion fur T n displaystyle T n nbsp a displaystyle a nbsp Anzahl der Unterprobleme in der Rekursion 1 b displaystyle 1 b nbsp Teil des Originalproblems welches wiederum durch alle Unterprobleme reprasentiert wird f n displaystyle f n nbsp Kosten Aufwand Nebenkosten die durch die Division des Problems und die Kombination der Teillosungen entstehenDas Master Theorem unterscheidet drei Falle wobei sich hochstens ein Fall auf die gegebene Rekursion anwenden lasst Passt keiner der Falle so lasst sich das Master Theorem nicht anwenden und man muss sich anderer Methoden bedienen Erster Fall Zweiter Fall Dritter FallAllgemeinFalls gilt f n O n log b a e displaystyle f n in mathcal O left n log b a varepsilon right nbsp fur ein e gt 0 displaystyle varepsilon gt 0 nbsp f n 8 n log b a displaystyle f n in Theta left n log b a right nbsp f n W n log b a e displaystyle f n in Omega left n log b a varepsilon right nbsp fur ein e gt 0 displaystyle varepsilon gt 0 nbsp und ebenfalls fur ein c displaystyle c nbsp mit 0 lt c lt 1 displaystyle 0 lt c lt 1 nbsp und alle hinreichend grossen n displaystyle n nbsp gilt a f n b c f n displaystyle af textstyle frac n b leq cf n nbsp Dann folgt T n 8 n log b a displaystyle T n in Theta left n log b a right nbsp T n 8 n log b a log n displaystyle T n in Theta left n log b a log n right nbsp T n 8 f n displaystyle T n in Theta f n nbsp Beispiel T n 8 T n 2 1000 n 2 displaystyle T n 8T textstyle frac n 2 1000n 2 nbsp T n 2 T n 2 10 n displaystyle T n 2T textstyle frac n 2 10n nbsp T n 2 T n 2 n 2 displaystyle T n 2T textstyle frac n 2 n 2 nbsp Aus der Formel ist folgendes abzulesen a 8 displaystyle a 8 nbsp b 2 displaystyle b 2 nbsp f n 1000 n 2 displaystyle f n 1000n 2 nbsp log b a log 2 8 3 displaystyle log b a log 2 8 3 nbsp a 2 displaystyle a 2 nbsp b 2 displaystyle b 2 nbsp f n 10 n displaystyle f n 10n nbsp log b a log 2 2 1 displaystyle log b a log 2 2 1 nbsp a 2 displaystyle a 2 nbsp b 2 displaystyle b 2 nbsp f n n 2 displaystyle f n n 2 nbsp log b a log 2 2 1 displaystyle log b a log 2 2 1 nbsp 1 Bedingung f n O n log b a e displaystyle f n in mathcal O left n log b a varepsilon right nbsp fur ein e gt 0 displaystyle varepsilon gt 0 nbsp f n 8 n log b a displaystyle f n in Theta left n log b a right nbsp f n W n log b a e displaystyle f n in Omega left n log b a varepsilon right nbsp fur ein e gt 0 displaystyle varepsilon gt 0 nbsp Werte einsetzen 1000 n 2 O n 3 e displaystyle 1000n 2 in mathcal O left n 3 varepsilon right nbsp 10 n 8 n 1 displaystyle 10n in Theta left n 1 right nbsp n 2 W n 1 e displaystyle n 2 in Omega left n 1 varepsilon right nbsp Wahle e gt 0 displaystyle varepsilon gt 0 nbsp 1000 n 2 O n 2 displaystyle 1000n 2 in mathcal O left n 2 right nbsp mit e 1 displaystyle varepsilon 1 nbsp 10 n 8 n displaystyle 10n in Theta left n right nbsp n 2 W n 2 displaystyle n 2 in Omega left n 2 right nbsp mit e 1 displaystyle varepsilon 1 nbsp 2 Bedingung nur im 3 Fall a f n b c f n displaystyle af textstyle frac n b leq cf n nbsp Setze auch hier obige Werte ein 2 n 2 2 c n 2 displaystyle 2 textstyle frac n 2 2 leq cn 2 Leftrightarrow nbsp 1 2 n 2 c n 2 displaystyle textstyle frac 1 2 n 2 leq cn 2 nbsp Wahle c n 1 1 2 n 2 1 2 n 2 displaystyle forall n geq 1 textstyle frac 1 2 n 2 leq textstyle frac 1 2 n 2 nbsp Damit gilt fur die Laufzeitfunktion T n 8 n 3 displaystyle T n in Theta n 3 nbsp T n 8 n log n displaystyle T n in Theta n log n nbsp T n 8 n 2 displaystyle T n in Theta n 2 nbsp Wahre Aussage Verallgemeinerung des zweiten Falls BearbeitenNicht alle Rekurrenzgleichungen lassen sich mithilfe einer der drei Fallen des Mastertheorems losen So ist zum Beispiel die folgende Rekurrenzgleichung nicht direkt mit dem Mastertheorem losbar T n 8 T n 2 n 3 ln n displaystyle T n 8T textstyle frac n 2 n 3 ln n nbsp Auf den ersten Blick scheint es dass der 3 Fall anzuwenden ist a 8 displaystyle a 8 nbsp b 2 displaystyle b 2 nbsp f n n 3 ln n displaystyle f n n 3 ln n nbsp Fur den 3 Fall ist zu zeigen f n W n log b a e displaystyle f n in Omega left n log b a varepsilon right nbsp Definition vom W Kalkul f n W g n 0 lt lim inf n f n g n displaystyle f n in Omega g n 0 lt liminf n to infty left textstyle frac f n g n right leq infty nbsp Angewandt auf n 3 ln n W n log 2 8 e displaystyle n 3 ln n in Omega left n log 2 8 varepsilon right nbsp e gt 0 0 lt lim inf n f n g n lim inf n n 3 ln n n log 2 8 e lim inf n ln n n e 0 displaystyle exists varepsilon gt 0 0 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 nbsp Widerspruch Es existiert kein e gt 0 displaystyle varepsilon gt 0 nbsp so dass der Limes ungleich Null ist Also ist der 3 Fall nicht auf diese Rekursionsgleichung anwendbar Es gilt T n 8 n log b a ln k 1 n displaystyle T n in Theta left n log b a ln k 1 n right nbsp falls f n 8 n log b a ln k n displaystyle f n in Theta left n log b a ln k n right nbsp Genau betrachtet stellt diese Formel eine Verallgemeinerung des zweiten Falls dar Losung nach obiger Formel f n n 3 ln n 8 n log b a ln k n 8 n log 2 8 ln 1 n 8 n 3 ln n displaystyle 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 nbsp Da f n displaystyle f n nbsp die hinreichende Bedingung erfullt gilt nun T n 8 n 3 ln 2 n displaystyle T n Theta left n 3 ln 2 n right nbsp Siehe zu demselben Beispiel auch die Aufwandsabschatzung im O Kalkul mit Hilfe der Substitutionsmethode Bemerkungen BearbeitenAngenommen es ist folgende Rekurrenz gegeben bei der n b displaystyle n b nbsp durch die Floor oder Ceiling Funktion angegeben werden z B T n a T n b f n displaystyle T n aT lfloor tfrac n b rfloor f n nbsp In diesem Fall kann man n b displaystyle lfloor tfrac n b rfloor nbsp oder auch n b displaystyle lceil tfrac n b rceil nbsp mit Hilfe der Form n b displaystyle tfrac n b nbsp abschatzen Ob man nun T n 8 ln n displaystyle T n in Theta ln n nbsp Logarithmus naturalis schreibt oder T n 8 lg n displaystyle T n in Theta lg n nbsp dekadischer Logarithmus ist egal da nach den Logarithmengesetzen gilt ln n log e n log 10 n log 10 e c log 10 n 8 log 10 n 8 lg n 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 nbsp Allgemeinere Form BearbeitenIn allgemeinerer Form gilt auch Definition Bearbeiten Sei T N 0 N 0 displaystyle T mathbb N 0 to mathbb N 0 nbsp die zu untersuchende Abbildung der Form T n i 1 m T a i n f n displaystyle T n sum i 1 m T left alpha i n right f n nbsp wobei a i R 0 lt a i lt 1 displaystyle alpha i in mathbb R 0 lt alpha i lt 1 nbsp m N m 1 displaystyle m in mathbb N m geq 1 nbsp und f n 8 n k displaystyle f n in Theta n k nbsp mit k N 0 displaystyle k in mathbb N 0 nbsp T displaystyle T nbsp wird hierfur implizit durch T x T x displaystyle T x T lfloor x rfloor nbsp oder T x displaystyle T lceil x rceil nbsp fur x R 0 displaystyle x in mathbb R 0 nbsp auf die reellen Zahlen fortgesetzt Dann gilt T n 8 n k falls i 1 m a i k lt 1 8 n k log n falls i 1 m a i k 1 8 n c mit i 1 m a i c 1 falls i 1 m a i k gt 1 displaystyle T n in begin cases Theta n k amp mbox falls sum i 1 m alpha i k lt 1 Theta n k log n 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 mbox falls sum i 1 m alpha i k gt 1 end cases nbsp Beispiel BearbeitenMergesort Bearbeiten Als Beispiel fur die Berechnung der Laufzeit eines rekursiven Algorithmus mit Hilfe des Master Theorem betrachten wir das rekursive Sortierverfahren Mergesort Mergesort besitzt folgende Rekursionsgleichung T n 2 T n 2 c n displaystyle T n 2 cdot T textstyle frac n 2 c cdot n nbsp Wahle a 2 displaystyle a 2 nbsp b 2 displaystyle b 2 nbsp und f n c n displaystyle f n c cdot n nbsp Es folgt log b a log 2 2 1 displaystyle log b a log 2 2 1 nbsp Nach dem Master Theorem folgt dass Mergesort folgende Laufzeit besitzt T n 8 n log n displaystyle T n in Theta n cdot log n nbsp Literatur BearbeitenThomas H Cormen Charles E Leiserson Ronald L Rivest Clifford Stein Algorithmen eine Einfuhrung Oldenbourg Munchen Wien 2004 ISBN 3 486 27515 1 englisch Introduction to algorithms Ubersetzt 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 Abgerufen von https de wikipedia org w index php title Master Theorem amp oldid 235607253
