Kurs:Algorithmen und Datenstrukturen/Vorlesung/Mastertheorem

Mastertheorem

Auf dieser Seite wird das Master Theorem behandelt. Die Mastermethode ist ein „Kochrezept“ zur Lösung von Rekursionsgleichungen der Form:

$T(n)=aT(n/b)+f(n)$ mit den Konstanten $a\ge 1undb>1$, f(n) ist eine asymptotische, positive Funktion, d.h. $f(n)>0\mathrm{\forall }n>n_0$

• a steht dabei für die Anzahl der Unterprobleme.

• n/b ist die Größe eines Unterproblems

• T(n/b) ist der Aufwand zum Lösen eines Unterproblems (der Größe n/b)

• f(n) ist der Aufwand für das Zerlegen und Kombinieren in bzw. von Unterproblemen

Bei der Mastermethode handelt es sich um ein schnelles Lösungsverfahren zur Bestimmung der Laufzeitklasse einer gegebenen rekursiv definierten Funktion. Dabei gibt es 3 gängige Fälle:

• Fall 1: Obere Abschätzung
• Fall 2: Exakte Abschätzung
• Fall 3: Untere Abschätzung

Lässt sich keiner dieser 3 Fälle anwenden, so muss die Komplexität anderweitig bestimmt werden und wir müssen Voraussetzungen für die Anwendung des Mastertheorems überprüfen.

Dafür vergleicht man $f(n)$ mit $n^{lo{g}_{b}a}$. Wir verstehen n/b als $⌞n/b⌟oder⌜n/b⌝$. Im Folgenden verwenden wir die verkürzte Notation $lo{g}_{2}nalsldn$.

Fall 1

Wenn $f(n)\in O(n^{lo{g}_{b}a-ϵ})\text{für ein }ϵ>0$. Daraus folgt, dass f(n) polynomiell langsamer wächst als $n^{lo{g}_{b}a}$ um einen Faktor $n^{ϵ}$. Damit haben wir die Lösung $T(n)=\mathrm{\Theta }(n^{lo{g}_{b}a})$.

Fall 2

Wenn $f(n)\in \mathrm{\Theta }(n^{lo{g}_{b}a}\cdot l{d}^{k}n)\text{für ein }k\ge 0$. Daraus folgt, dass f(n) und $n^{lo{g}_{b}a}\cdot l{d}^{k}n$ vergleichbar schnell wachsen. Damit haben wir die Lösung $T(n)=\mathrm{\Theta }(n^{lo{g}_{b}a}\cdot l{d}^{k+1}n)$.

Fall 3

Wenn $f(n)\in \mathrm{\Omega }(n^{lo{g}_{b}a+ϵ})\text{für ein }ϵ>0$ und die Regularitätsbedingung $a\cdot f(n/b)\le c\cdot f(n)$ für eine Konstante $c\in (0,1)$ und genügend große n erfüllt. Daraus folgt, dass f(n) polynomiell schneller wächst als $n^{lo{g}_{b}a}$ um einen Faktor $n^{ϵ}$ und f(n) erfüllt die sogenannte Regularitätsbedingung. Damit haben wir die Lösung $T(n)\in \mathrm{\Theta }(f(n))$.

Bedeutung

In jedem Fall vergleichen wir f(n) mit $n^{lo{b}_{b}a}$. Intuitiv kann man sagen, dass die Lösung durch die größere Funktion bestimmt wird. Im zweiten Fall wachsen sie ungefähr gleich schnell. Im ersten und dritten Fall muss f(n) nicht nur kleiner oder größer als $n^{lo{b}_{b}a}$ sein, sondern auch polynomiell kleiner oder größer um einen Faktor $n^{ϵ}$. Der dritte Fall kann nur angewandt werden, wenn die Regularitätsbedingung erfüllt ist.

Regularitätsbedingung

Doch wozu wird die Regularitätsbedingung benötigt? Zur Erinnerung, im dritten Fall dominiert f(n) das Wachstum von T(n). Wir müssen an dieser Stelle sicherstellen, dass auch bei rekursivem Anwenden, also wenn die Argumente kleiner werden, T(n) von f(n) dominiert wird. Veranschaulicht heißt das:

$T(n)=aT(n/b)+f(n)$

$=a(aT(n/b^2)+f(n/b))+f(n)$

$=a^{2}T(n/b^2)+af(n/b)+f(n)$

für $af(n/b)\le cf(n)(c\in (0,1))$ Das Wachstum muss durch f(n) dominiert werden und darf f(n) nicht dominieren.

Die Regularitätsbedingung gilt wenn sie für f(n) und g(n) gilt auch für $f(n)\cdot g(n)$ und auch für $f(n)+g(n)$

Nachweis für $f(n)\cdot g(n)$

Voraussetzung ist, dass die Regularitätsbedingung für f(n) und g(n) gilt, d.h.:

$\mathrm{\exists }{c}_1\in (0,1),\mathrm{\exists }{n}_1\in \mathbb{N}\mathrm{\forall }n\ge n_1:af(n/b)\le c_{1}f(n)$

$\mathrm{\exists }{c}_2\in (0,1),\mathrm{\exists }{n}_2\in \mathbb{N}\mathrm{\forall }n\ge n_2:ag(n/b)\le c_{2}g(n)$

Für $(f\cdot g)(n)$ gilt:

$a(f\cdot g)(n/b)=af(n/b)\cdot ag(n/b)$

man wählt $c=c_1\cdot c_2\in (0,1)$

und $n_0=max\{n_1,n_2\}$

$\mathrm{\forall }n\ge n_0:af(n/b)\cdot ag(n/b)\le c_{1}f(n)\cdot c_{2}g(n)=c(f\cdot g)(n)$

Nachweis für $f(n)+g(n)$

Voraussetzung ist, dass die Regularitätsbedingung für f(n) und g(n) gilt, d.h.:

$\mathrm{\exists }{c}_1\in (0,1),\mathrm{\exists }{n}_1\in \mathbb{N}\mathrm{\forall }n\ge n_1:af(n/b)\le c_{1}f(n)$

$\mathrm{\exists }{c}_2\in (0,1),\mathrm{\exists }{n}_2\in \mathbb{N}\mathrm{\forall }n\ge n_2:ag(n/b)\le c_{2}g(n)$

Für $(f+g)(n)$ gilt:

$a(f+g)(n/b)=af(n/b)+ag(n/b)$

man wählt $c=max\{c_1,c_2\}$

und $n_0=max\{n_1,n_2\}$

$\mathrm{\forall }n\ge n_0:af(n/b)+ag(n/b)\le c_{1}f(n)+c_{2}g(n)\le c(f+g)(n)$

Überblick

Ist T(n) eine rekursiv definierte Funktion der Form

$T(n)=aT(n/b)+f(n)mita\ge 1,b>1,\mathrm{\forall }n>n_0:f(n)>0$

Dann gilt:

• 1. Fall: Wenn $f(n)\in O(n^{lo{g}_{b}a-ϵ})\text{für ein }ϵ>0dannT(n)=\mathrm{\Theta }(n^{lo{g}_{b}a})$
• 2. Fall: Wenn $f(n)\in \mathrm{\Theta }(n^{lo{g}_{b}a}\cdot l{d}^{k}n)\text{für ein }k\ge 0dannT(n)=\mathrm{\Theta }(n^{lo{g}_{b}a}\cdot l{d}^{k+1}n)$
• 3. Fall: Wenn $f(n)\in \mathrm{\Omega }(n^{lo{g}_{b}a+ϵ})\text{für ein}ϵ>0$ und $a\cdot f(n/b)\le c\cdot f(n)\text{für eine Konstante }c\in (0,1)$ und genügend große n dann $T(n)=\mathrm{\Theta }(f(n))$

Idee

Wir haben folgenden Rekursionsbaum:

Auf der ersten Ebene ist der Aufwand f(n), auf der zweiten Ebene $af(n/b)$ und auf der dritten Ebene $a^{2}f(n/b^2)$. Die Höhe des Baumes beträgt $h=lo{g}_{b}n$. Die Anzahl der Blätter berechnet sich durch $a^h$ und beträgt somit $a^{lo{g}_{b}n}=n^{lo{g}_{b}a}$.

Fall 1: Das Gewicht wächst geometrisch von der Wurzel zu den Blättern. Die Blätter erhalten einen konstanten Anteil des Gesamtgewichts.

$\mathrm{\Theta }(n^{lo{g}_{b}a})$

Fall 2: k ist 0 und das Gewicht ist ungefähr das Gleiche auf jedem der $lo{g}_{b}a$ Ebenen.

$\mathrm{\Theta }(n^{lo{g}_{b}a}\cdot ldn)$

Fall 3: Das Gewicht reduziert sich geometrisch von der Wurzel zu den Blättern. Die Wurzel erhält einen konstanten Anteil am Gesamtgewicht.

$\mathrm{\Theta }(f(n))$

Beispiel 1

$T(n)=4T(n/2)+n$

$a=4,b=2\Rightarrow n^{lo{g}_{b}a}=n^{lo{g}_{2}4}=n^2$

$f(n)=n$

Fall 1: $f(n)\in O(n^{2-ϵ})\text{für }ϵ>0$

$\Rightarrow T(n)=\mathrm{\Theta }(n^2)$

Beispiel 2

$T(n)=4T(n/2)+n^2$

$a=4,b=2\Rightarrow n^{lo{g}_{b}a}=n^{lo{g}_{2}4}=n^2$

$f(n)=n^2$

Fall 2: $f(n)\in \mathrm{\Theta }(n^{2}l{d}^{k}n)\text{für }k=0$

$\Rightarrow T(n)=\mathrm{\Theta }(n^{2}ldn)$

Beispiel 3

$T(n)=4T(n/2)+n^3$

$a=4,b=2\Rightarrow n^{lo{g}_{b}a}=n^{lo{g}_{2}4}=n^2$

$f(n)=n^3$

Fall 3: $f(n)\in \mathrm{\Omega }(n^{2+ϵ})\text{für }ϵ>0$

und $4(\frac{n}{2}{)}^3\le c{n}^3$ (Regularitätsbedingung)

für $c=\frac{1}{2}$

$\Rightarrow T(n)=\mathrm{\Theta }(n^3)$

Beispiel 4

$T(n)=4T(n/2)+\frac{n^2}{logn}$

$a=4,b=2\Rightarrow n^{lo{g}_{b}a}=n^{lo{g}_{2}4}=n^2$

$f(n)=\frac{n^2}{logn}$

Welcher Fall liegt nun vor? Das Mastertheorem kann an dieser Stelle nicht benutzt werden, da

• 1. Fall $f(n)\notin O(n^{2-ϵ})$
• 2. Fall $f(n)\notin \mathrm{\Theta }(n^2\cdot l{d}^{k}n)\text{ für }k\ge 0$
• 3. Fall $f(n)\notin \mathrm{\Omega }(n^{2+ϵ})$

Nützliche Hinweise

• Basisumrechnung

$lo{g}_{b}x=\frac{lo{g}_{a}x}{lo{g}_{a}b}\Rightarrow O(lo{g}_{b}x)=O(lo{g}_{a}x)$

• de L'Hospital

$li{m}_{x\to \mathrm{\infty }}\frac{f(x)}{g(x)}=li{m}_{x\to \mathrm{\infty }}\frac{f^{\prime }(x)}{g^{\prime }(x)}$

• Vergleiche Logarithmus vs. Polynom

$li{m}_{x\to \mathrm{\infty }}lo{g}_{b}x=\mathrm{\infty }$

$li{m}_{x\to \mathrm{\infty }}{x}^{ϵ}=\mathrm{\infty }\text{ für }ϵ>0$

$li{m}_{x\to \mathrm{\infty }}\frac{lo{g}_{b}x}{x^{ϵ}}=li{m}_{x\to \mathrm{\infty }}\frac{(lo{g}_{b}x{)}^{\prime }}{(x^{ϵ}{)}^{\prime }}=li{m}_{x\to \mathrm{\infty }}\frac{\frac{1}{x}}{ϵx^{ϵ-1}}$ $=li{m}_{x\to \mathrm{\infty }}\frac{1}{xϵx^{ϵ-1}}=li{m}_{x\to \mathrm{\infty }}\frac{1}{ϵx^{ϵ}}=0\text{ für }ϵ>0$