cards-deck: 100-199_university::111-120_theoretic_cs::111_algorithms_datastructures

Master Theorem | solving simple recurrence relations:

anchored to [[111.00_anchor]]

Overview:

Das Master-Theorem kann angewandt werden um die Einordnung einer Laufzeitklasse bei einer rekursiv definierten Funktion bestimmen zu können.

[!Warning] Nicht jede rekursive Funktion kann mit diesem bestimmt werden.

In unserem Kontext haben wir etwa bei der Anwendung von Divide-And-Conquer-Algorithmen oft eine solche Struktur, die Probleme nach und nach in kleinere aufteilt und dabei rekursiv agiert.

Definition:

Die allgemeine Form des Master-Theorem wird folgend beschrieben: $$T(n)=a\cdot T\left(\frac{n}{b}\right)+f(n)$$ wie wir sie angewandt, was bedeuten ihre Parameter? #card wobei folgend:

• $T(n)$ die Laufzeitfunktion
• $a,b$ Konstanten mit $a\ge 1,b>1$
  • $a$ beschreibt die Anzahl an Unterproblemen in der Rekursion
  • $\frac{1}{b}$ stellt einen Teil des Originalproblemes dar, wobei es durch all seine Unterprobleme repräsentiert wird
• $f(n)$ die Funktion darstellt und beschreibt, welchen Aufwand, oder welche Nebenkosten durch das Teilen des Problems, und dem Kombinieren der Teillösungen aufkommen. ^1704708610210

[!Important] Betrachtung zu $a.b$ was müssen wir bei diesen Parametern beachten? #card $a,b$ dürfen nicht von $n$ ( also der Größe des Problemes) abhängen! ^1704708610218

Um diese Faktoren entsprechend bestimmen zu können, wäre es wohl sinnvoll Divide-and-Conquer zu betrachten:

Divide and Conquer:

Angenommen wir haben ein Problem der Größe $n$. Normalerweise kann es jetzt sein, dass gestellte Problem mit $n$ Berechnungen oder ähnlichem gelöst werden kann, aber vielleicht sehr langsam ist bzw schlecht mit hohen $n$ skaliert. Wir wollen also folgend das Groß Problem in kleinere Probleme aufteilen.

Bei Divide and Conquer folgen wir immer dem gleichen Prinzip zur Analyse der Laufzeit:

1. $T(n)$ beschreibt die gesamte Laufzeit in Abhängigkeit von $n$.
2. Wir haben jetzt $a$ Subprobleme, die wir aus dem großen Problem erzeugen.
3. $b$ beschreibt den Faktor, mit welchem die Subprobleme aufgebaut werden. Daraus können wir etwa die Größe eines Subproblemes bestimmen: $m:=\frac{n}{b}$
4. Wir gehen davon aus, dass die Kombination der Teillösungen $\mathcal{O}(n^d)$ Zeit benötigt.

Aus dieser Betrachtung können wir jetzt die obige Formel konstruieren: $$T(n_{)}=a\cdot T(\lceil \frac{n}{b}\rceil )+\mathcal{O}(n^d)$$

Master-Theorem | Folgerung:

Wir können aus dieser Betrachtung jetzt 3 Fälle erzeugen: Betrachte hierfür nochmals das Theorem: $$T(n_{)}=a\cdot T(\lceil \frac{n}{b}\rceil )+\mathcal{O}(n^d)$$Dafür gelte, dass $a>1,b>1,d\ge 0$, dann folgt: welche und was sagen sie uns? #card Fall 1: $f(n)\in \mathcal{O}(n^{{\log }_{b}a-\psi ),}\psi >0$ oder auch $d<{\log }_{b}a$ folgt: $T(n)=\mathcal{O}(n^{{\log }_{b}a})$ –> das kommt daher, dass der log aus ${\log }_{b}a$ größer ist, als der Exponent der Funktion $f(n)$ wodurch wir dann wissen, dass die Laufzeit nicht von der Funktion $f(n)$ bedingt wird! Fall 2: $f(n)\in \Theta (n^{{\log }_{b}a})\vee d={\log }_{b}a$ und es folgt : $T(n)=\mathcal{O}(n^d\cdot \log n)\vee n^{{\log }_{b}a}\cdot \log n$ –> das kommt daher, dass hier die Funktion $f(n)$ genauso schnell schnell wächst, wie der Rest, wodurch wir die Laufzeit bestimmen können. Es gibt hier auch noch einen Spezialfall, der manchmal angewandt werden kann! Fall 3: $f(n)\in \Omega (n^{{\log }_{b}a+\psi })\vee \in \mathcal{O}(n^d)$ wobei wir hier aufteilen müssen:

• $f(n)\in \Omega (n^{{\log }_{b}a+\psi }),\psi >0\wedge a\cdot f\left(\frac{n}{b}\right)\le c\cdot f(n),c<1$ –> um die erste Aussage zu zeigen
• oder einfach $d>lo{g}_{b}a$ Folgt jetzt: $T(n)=\Theta (f(n))$ bzw. auch einfach beschrieben als $T(n)=\Theta (n^d)$, weil $d$ ja den Exponent der Funktion $f(n)$ angibt! ^1704708610222

[!Important] Spezialfall für Fall 2: Wenn wir etwa einen logarithmus in der Funktion $f(n)$ haben, können wir manchmal das Master-Theorem trotzdem anwenden!

Dafür muss folgendes gelten: $$f(n)\in \Theta (n^{{\log }_{b}a}\cdot {\ln }^k\cdot n),k>0$$ oder anders formuliert: $$f(n)\in \Theta (n^c\cdot {\log }^k\cdot n),c={\log }_{b}a$$ Können wir also unsere Funktion $f(n)$ mit der obigen Schreibweise darstellen bzw. stimmt sie überein, können wir das Master-Theorem anwenden!

Es folgt hier jetzt $$⟹T(n)\in \Theta (n^{{\log }_{b}a}{\ln }^{k+1}\cdot n)$$ Wichtig ist hier, dass der ln in seiner Potenz um eins erhöht wird!

Trick | Logarithm conversion:

Bedenke, dass wir den Logarithmus entsprechend konvertieren können:$${\log }_{a}x=\frac{{\log }_b(n)}{{\log }_b(a)}$$ und weiter auch: $${\log }_b(x)={\log }_b(a^{{\log }_a(x)})={\log }_a(x)\cdot {\log }_b(a)$$

Beweis des master theorem:

Um das Master-Theorem zu beweisen, kann man das Problem in Form eines Baumes betrachten und daraus das Prinzip Stufe für Stufe betrachten.

Wir wollen dafür ein Problem der Größe $n$ betrachten und es via Divide-and-Conquer in $\frac{n}{b}$ Probleme aufteilen. ![[Pasted image 20221024142928.png]] Was wir hier sehen können:

• Ein großes Problem wird in $b$-viele kleinere Probleme aufgeteilt.
• mit $a$ wird angegeben, wie viele Brnaches wir pro Stufe erzeugen werden.
• jedes der $b$ Probleme wird anschließend wieder in $b$ teile aufgeteilt.
  • Dadurch haben wir ab der zweiten Stufe bereits $\frac{2}{b^2}$ Probleme
• Dieser Prozess teilt sich weiter und weiter in kleinere Probleme auf
• bis wir Probleme der Größe $1$ erhalten

Wenn wir jetzt die Probleme auf unterster Ebene gelöst haben, müssen sie wieder zusammengefasst werden: Die Kosten für jede Berechnung aus dem unterem zum oberen Level ( also das Kombinieren der Lösungen) brauch $\left({\frac{n}{b}}^d\right)$.

Tiefe des Baumes:

Wir möchten jetzt betrachten, wie viele Ebenen wir brauchen, um das Ende des Baumes zu erreichen. Wir wissen, dass das Problem mit jeder Stufe kleiner wird. wie lang benötigen wir jetzt, um bis zum Grund des Baumes zu kommen? #card Wir wollen folgend lösen, ab wann gilt“ $\frac{n}{b^{height}}=1$, und müssen also height bestimmen = ${\log }_{b}n$ –> die Menge an Ebenen, ist also abhängig von $b$! ^1704708610226

Stufe $k$ in Ebene:

Auf jeder Stufe $k$ des Baumes müssen wir bestimmte Dinge beachten:

1. Auf Ebene $k$ haben wir insgesamt $a^k$ subprobleme ( also die Breite des Baumes wird damit beschrieben.)
2. Jedes dieser Subprobleme hat hierbei eine Größe von $n_k:=\frac{n}{b^k}$
3. Grundsätzlich wird auf der Ebene keine extra Arbeit verursacht! Sie entsteht nur durch das Kombinieren der Lösungen darunter.
   1. Es werden jetzt $k$ weitere Subprobleme aufgerufen und diese wiederholen den Prozess.

[!Important] Recombination pro Stufe kostet! Jede Stufe hat weitere Probleme unter sich, wobei ihre Lösungen wieder kombiniert werden müssen. Dieser Prozess kostet Zeit, die wir folgend beschreiben können: wie? #card $$\mathcal{O}((n_k^d))=\mathcal{O}({\left(\frac{n}{b^l}\right)}^d)$$ Dieser Vorgang wird für jedes Probleme durchgeführt, also haben wir am Ende eine erweiterte Laufzeit: $$\mathcal{O}\left(a^k\cdot {\left(\frac{n}{b^k}\right)}^d\right)=\mathcal{O}\left(n^d\cdot {\left(\frac{a}{b^d}\right)}^k\right)$$ ^1704708610230

Boden des Baumes:

Wir können die Menge von Problemen am Boden des Baumes (also der untersten Ebene unserer Problem-Aufteilung) folgend bestimmen: #card $a^{height}=a^{{\log }_{b}n}=n^{{\log }_{b}a}$ Wir wissen, dass jedes dieser Probleme in der Komplexität $\Theta (1)$ entspricht. $|⟹$ brauchen wir jetzt $\Theta (n^{{\log }_{b}a})$ Zeit für die unterste Stufe! ^1704708610234

Gesammelte Zeit für den Divide-And-Conquer-Baum:

Wir haben jetzt alle Ebenen und Schritte zur Bildung der Lösung betrachtet. Aus den einzelnen Ergebnissen können wir jetzt aufbauen, wie die gesamte Laufzeit aussehen muss: #card

[!Info] Aufbau der Gesamtzeit: $$T(n)=\left(\sum _{k=0}^{height-1}\mathcal{O}\left(n^d\cdot {\left(\frac{a}{b^d}\right)}^k\right)\right)+\mathcal{O}(n^{{\log }_{b}a})$$ Wir können sie aber besser konstruieren bzw. umstruktieren: $$T(n)=\mathcal{O}(n^d)\cdot \mathcal{O}\left(\sum _{k=0}^{{\log }_b(n)-1}{\left(\frac{a}{b^d}\right)}^k\right)+\mathcal{O}(n^{{\log }_{b}a})$$ die Summe entspricht hierbei der [[math1_Folgen#Beispiel ==Geometrische Folge==|geometrischer Folge]] bzw Reihe und wird demnach folgende Zustände haben: $\mathcal{O}(1)$, wenn $c<1$. $\mathcal{O}(m)$, wenn $c=1$ $\mathcal{O}(c^m)$, wenn $c>1$ Da wir bei uns folgenden Zustand haben, können wir die 3 Fälle aus der Definition resultieren! $c=\frac{a}{b^d}$, sowie $m={\log }_b(n)-1$ ^1704708610239

Beispiel:

Betrachten wir die naive Implementation der Integer-Multiplikation nochmal [[111.04_laufzeitanalyse_onotation#Beispiele zur Bestimmung der Laufzeit]]. Wir resultieren hier mit $$T(n)=4\cdot T\left(\frac{n}{2}\right)+\mathcal{O}(n)$$ Hier haben wir jetzt folgende Attribute: $d=1⟹\mathcal{O}(n^1)$ $a=4$, $b=2$ Wenn wir jetzt die 3 Fälle betrachten: ${\log }_{2}4=2>1=d$ und somit ist $d<{\log }_{2}4$ also haben wir den dritten Fall erreicht. Daraus folgt jetzt die Laufzeit: $$T_n=\mathcal{O}(n^{{\log }_{b}a})=\mathcal{O}(n^2)$$