Rekurrenzen und das Master-Theorem

Ein kurzer Ausflug zu Divide-and-Conquer Algorithmen

Divide-and-Conquer Algorithmen teilen große Probleminstanzen rekursiv auf (divide) bis die Teilinstanzen klein genug sind, um sie direkt zu lösen (conquer). Danach werden aber die rekursiv erzeugten Lösungen der Teilinstanzen noch zur Lösung der Gesamtinstanz zusammengesetzt bzw. verschmolzen (merge). Ein Divide-and-Conquer-Algorithmus besteht somit meist aus den Schritten divide + conquer + merge.

Prinzipiell entstehen bei einem Divide-and-Conquer-Algorithmus Kosten für das Aufteilen der Instanz in kleinere Instanzen (d.h. für das divide), Kosten für das Lösen der kleinen Instanzen, d.h. für die Fälle, in denen die Rekursion abbricht (d.h. für das conquer) und Kosten für das Zusammensetzen der Teilösungen zur Gesamtlösung (d.h. für das merge). Wichtig ist, dass die Kosten für das Aufteilen und Zusammensetzen jeweils von der aktuellen Problemgröße abhängen und im Verlauf des Algorithmus sehr viele divide und merge Schritte vorkommen können. Um die Struktur hervorzuheben, kann man dies meist recht leicht mit Hilfe eines Rekursionsbaumes visualisieren.

Angenommen wir haben einen Divide-and-Conquer-Algorithmus für eine Eingabe der Größe \(n\). Stellen wir uns nun vor, dass unser Algorithmus dieses Problem in \(k\) kleinere Instanzen der Größe \(m \lt n\) aufteilt. Diese werden wiederum jeweils in \(k\) noch kleinere Instanzen der Größe \(l \lt m\) aufgeteilt usw. bis wir bei Instanzen der Größe \(2\) ankommen. Diese werden dann direkt gelöst und die Lösungen von jeweils \(k\) vielen dieser Instanzen werden dann zur Lösung der entsprechenden Instanz, von der diese \(k\) Instanzen abstammen, zusammengesetzt. Dies setzt sich dann weiter fort, bis die Lösung für die Gesamtinstanz erzeugt wird.

Sei \(T(n)\) die Kosten für das Lösen einer Instanz der Größe \(n\), dann erhalten wir folgendes Gesamtbild:

Angenommen die Kosten für das divide einer Instanz der Größe \(n\) sind \(f(n)\) und die Kosten für das merge von \(k\) Teillösungen zu einer Lösung für eine Instanz der Größe \(n\) sind \(g(n)\). Somit haben wir: \[T(n) = kT(m) + f(n)+ g(n).\] Für \(T(m)\) gilt dann rekursiv, dass \[T(m) = kT(l) + f(m)+ g(m).\] Wenn wir nun \(T(m)\) in \(T(n)\) einsetzen, dann haben wir: \begin{align*}T(n) &= kT(m) + f(n)+ g(n)\\ &= k(kT(l) + f(m) + g(m)) + f(n) + g(n)\\ &= k^2T(l) + kf(m)+kg(m) + f(n) + g(n) \end{align*}

Wenn wir das fortführen, dann sehen wir, dass sich pro Ebene des Rekursionsbaums die Kosten für das divide und für das merge aufsummieren und der vordere Term immer kleiner wird, bis er den Abbruchfall \(T(2)\) erreicht. Insgesamt haben wir somit, dass die Gesamtkosten des Divide-and-Conquer Algorithmus sich aus der Summe der Kosten pro Ebene des Rekursionsbaumes zusammensetzen. Zu jeder Ebene, außer der letzten, gehören die Kosten für das divide und für das merge. Für die letzte Ebene, die sogenannte Blattebene, entstehen nur die Kosten für das conquer.

Rekurrenzen

Jeder Divide-and-Conquer Algorithmus liefert uns eine Rekurrenzgleichung, die spezifiziert, wie große Probleme in kleine Probleme aufgeteilt werden und wann die Rekursion abbricht. Wird das Problem der Größe \(n\) jedes mal in \(a\) Teilprobleme, welche alle Größe \(\frac{1}{b}\) des Originalproblems haben, zerlegt und kostet das Zerlegen und das spätere Zusammensetzen all dieser Teilprobleme und Teillösungen \(f(n)\) und kostet das conquer für Teilprobleme der Größe höchstens \(c\) jeweils \(g(n)\), dann erhalten wir folgende Rekurrenz: \begin{align*} T(n) &= a \cdot T\left(\frac{n}{b}\right) + f(n), &\text{für $n > c$}\\ T(n) &= g(n), &\text{für $n\leq c$}, \end{align*} wobei hier \(a,c\geq 1\) und \(b \gt 1\) gilt.

Unser Ziel ist, eine Aussage der Form \(T(n) \in \mathcal{O}(h(n))\), für irgendeine Funktion \(h(n)\) zu zeigen, d.h. wir suchen eine obere Schranke für die Gesamtkosten unseres Algorithmus. Das Problem ist hier, dass wir keine geschlossene Form für \(T(n)\) haben. Um aus einer Rekurrenzgleichung eine geschlossene Form herzuleiten, können wir zwei Ansätze wählen: Iteratives Einsetzen oder Analyse des Rekursionsbaumes.

Iteratives Einsetzen:

Wir setzen die Gleichung für \(T(n)\) mehrfach in sich selbst ein und wir vereinfachen, falls möglich die auftretenden Terme. Wenn wir dies einige Male gemacht haben, dann leiten wir aus unseren Beobachtungen eine Vermutung ab, wie sich die Gleichung nach \(i\)-maligem Einsetzen verhält. Diese Vermutung beweisen wir dann per Induktion. Wenn wir dies geschafft haben, dann müssen wir nur noch berechnen, wie oft wir rekursiv einsetzen müssen, um garantiert auf den Rekursionsabbruch zu treffen, d.h. bis unsere Teilprobleme klein genug sind, um sie direkt zu lösen. Haben wir dies ermittelt, dann müssen wir dies nur noch an Stelle des \(i\) in unsere allgemeine Version einsetzen, um eine geschlossene Form für \(T(n)\) zu erhalten.

Als Beispiel betrachten wir die folgende Rekurrenz: \begin{align*} T(n) &= 2 T\left(\frac{n}{2}\right) + \frac{n}{2}, &\text{für $n > 2$}\\ T(n) &= 1,&\text{für $n\leq 2$} \end{align*} Somit haben wir \(a = b = c = 2\), \(f(n) = \frac{n}{2}\) und \(g(n) = 1\).

Wir setzen iterativ ein: \begin{align*} T(n) &= 2 T\left(\frac{n}{2}\right) + \frac{n}{2} \\ &= 2 \left(2 T\left(\frac{n}{4}\right) + \frac{n}{4}\right) + \frac{n}{2} = 4 T\left(\frac{n}{4}\right) + 2 \cdot \frac{n}{2}\\ &= 4\left(2T\left(\frac{n}{8}\right) + \frac{n}{8}\right) + 2\cdot \frac{n}{2} = 8 T\left(\frac{n}{8}\right) + 3\cdot \frac{n}{2} \end{align*} Aus den Beobachtungen leiten wir folgende Vermutung ab: Nach \(i\)-maligem Einsetzen gilt \[T(n) = 2^i T\left(\frac{n}{2^i}\right) + i \cdot \frac{n}{2}.\] Wir verzichten hier auf den Korrektheitsbeweis für unsere Vermutung, dieser ist eine gute Aufgabe um Induktionsbeweise zu üben.

Wir überlegen uns, wie oft rekursive Aufrufe erzeugt werden können, bevor die Problemgröße so klein wird, dass wir das Problem direkt lösen können und somit die Rekursion abbricht. \[\frac{n}{2^i} \leq 2 \iff n \leq 2^{i+1} \iff \log_2 n -1 \leq i.\] Als letzten Schritt setzen wir \(i = \log_2 (n) -1\) in unsere Vermutung von oben ein: \begin{align*}T(n) &= 2^{\log_2 (n) -1} T\left(\frac{n}{2^{\log_2 (n) -1}}\right) + (\log_2 (n) -1)\cdot \frac{n}{2}\\ &= \frac{n}{2} T(2) + (\log_2 (n) -1)\cdot \frac{n}{2}\\ & = \log_2 (n) \cdot \frac{n}{2} \in \mathcal{O}(n\log n). \end{align*}

Analyse des Rekursionsbaumes:

Nun betrachten wir das ganze noch auf eine andere Art. Wir analysieren den sogenannten Rekursionsbaum. Dieser veranschaulicht die Anzahl und Größe der erzeugten rekursiven Aufrufe. Es ist ein \(a\)-närer Baum, in dessen Wurzel für die Kosten des Originalproblems, d.h. \(T(n)\), steht. Die \(a\) vielen Kinder der Wurzel enthalten dann die Kosten der erzeugten rekursiven Teilprobleme, usw.

Wir zeichnen uns den Rekursionsbaum für unser Problem und berechnen, welche kosten pro Level im Baum anfallen. Dabei schlagen wir die Kosten für das divide und merge jeweils dem vorhergehenden Level (d.h. dem Level in dem die entsprechenden Aufrufe generiert werden) zu. Das letzte Level (d.h. die Blätter im Baum) besteht dann nur noch aus den Kosten für das conquer. Dafür leiten wir eine allgemeine Formel für die Kosten im \(i\)-ten Level her und beweisen diese (per Induktion). Mit Hilfe der Regel können wir dann die Kosten aller Level ermitteln und nun müssen wir nur noch berechnen, wieviele Level im Baum vorkommen. Damit können wir dann eine geschlossene Formel für \(T(n)\) berechnen, indem wir die Kosten aller Level einfach aufsummieren.

In unserem Beispiel ergeben sich Kosten von \(\frac{n}{2}\) pro Level des Baumes (siehe Abbildung). Dies gilt auch für das unterste Level, da wir dort \(\frac{n}{2}\) viele Blätter haben, die jeweils conquer-Kosten von \(1\) bewirken. Für die Gesamtkosten müssen wir nur noch die Kosten aller Level aufsummieren: Wir haben \(\log_2 n\) viele Level (einschließlich Level \(0\)) und pro Level haben wir Kosten von \(\frac{n}{2}\). Insgesamt somit \(T(n) = \log (n) \cdot \frac{n}{2} \in \mathcal{O}(n\log n)\).

Zu beachten ist noch, dass wir in beiden Fällen angenommen haben, dass \(n\) eine Zweierpotenz ist. D.h. dass wir an jeder Stelle die aktuelle Problemgröße exakt halbieren konnten. In diesem Fall erhalten wir die größtmögliche Anzahl an Teilproblemen mit der jeweils größtmöglichen Größe. Somit haben wir die tatsächlichen Gesamtkosten für unser Problem höchstens etwas zu hoch angesetzt. Wir erhalten also mit beiden Techniken im Allgemeinen nur eine obere Schranke an die Gesamtkosten. Wollen wir auch eine untere Schranke, dann müssen wir zeigen, dass der Rekursionsbaum auch im besten Fall genügend Level hat und dass pro Level genügend hohe Kosten anfallen.

Übung:

Als Übungen betrachten wir, was passiert, wenn wir unsere Beispielrekurrenz leicht abwandeln. Dazu betrachten wir zum Einen die folgende Rekurrenz: \begin{align*} T(n) &= 2 T\left(\frac{n}{2}\right) + n^2, &\text{für $n > 2$}\\ T(n) &= 1,&\text{für $n\leq 2$} \end{align*} D.h. wir nehmen an, dass das divide oder merge merge ein deutlich schwierigeres Problem ist und dafür quadratische Kosten anfallen.

Als nächste Übung betrachten wir, was passiert, wenn wir die Anzahl der Teilprobleme erhöhen: \begin{align*} T(n) &= 3 T\left(\frac{n}{2}\right) + \frac{n}{2}, &\text{für $n > 2$}\\ T(n) &= 1,&\text{für $n\leq 2$} \end{align*}

Das Master-Theorem

Tatsächlich müssen wir oft nicht den teils beschwerlichen Weg über die beiden obigen Optionen gehen. Es gibt ein Theorem, welches uns bei der Analyse vieler (aber nicht aller) Rekurrenzen hilft. Wir verwenden das Theorem hier ohne Beweis.

Wir wenden das Master-Theorem direkt auf unsere erste Beispielrekurrenz an. Zur Erinnung, die Rekurrenz lautet: \begin{align*} T(n) &= 2 T\left(\frac{n}{2}\right) + \frac{n}{2}, &\text{für $n > 2$}\\ T(n) &= 1,&\text{für $n\leq 2$} \end{align*} D.h. wir haben \(a = 2\), \(b = 2\) und \(f(n) = \frac{n}{2}\). Offensichtlich gilt \[f(n) \in \Theta(n) = \Theta(n^{\log_b(a)}) = \Theta(n^{\log_2(2)}),\] da \(\log_2(2) = 1\). Somit sind wir in Fall \(2\) des Master-Theorems und dieser besagt, dass \(T(n) \in \Theta(n^{\log_2(2)}\log n) = \Theta(n\log n)\) gilt.

Übung

Wende das Master-Theorem auf die anderen beiden obigen Rekurrenzen an!

Was haben wir gelernt?

1. Divide-and-Conquer-Algorithmen liefern uns leicht eine Rekurrenzgleichung mit deren Hilfe wir eine obere Schranke an die Kosten des Algorithmus beweisen können.
2. Um eine Rekurrenzgleichung in geschlossene Form zu bringen, können wir iteratives Einsetzen oder die Analyse des Rekursionsbaumes verwenden.
3. Beim iterativen Einsetzen wird die Gleichung mehrfach in sich selbst eingesetzt. Danach muss darauf eine allgemeine Regel abgeleitet werden, welche Gleichung nach \(i\)-maligem Einsetzen entsteht. Dieser Regel muss (per Induktion) bewiesen werden. Nun muss nur noch das \(i\) bestimmt werden, welches zum Rekursionsabbruch führt. Für dieses \(i\) wird dann nochmals die allgemeine Regel ausrechnet und dies liefert uns dann die geschlossene Form.
4. Bei der Analyse des Rekursionsbaumes bestimmen wir die Kosten pro Level des Baumes und summieren diese dann über alle Level. Dazu müssen wir auch zeigen, wieviele Level es gibt und eine allgemeine Regel, wie die Kosten im \(i\)-ten Level aussehen. Diese Regel muss auch wieder (per Induktion) bewiesen werden.
5. Für viele (aber nicht alle) Rekurrenzen können wir mit Hilfe des Master-Theorems direkt die Kosten bestimmen.