Kurs:Algorithmen und Datenstrukturen (hsrw)/Vorlesung/Rekursionsbäume

Rekursionsbäume

Auf dieser Seite wird das Thema Rekursionsbäume behandelt. Das allgemeine Problem ist, dass man zum Abschätzen von der Aufwandsklasse einer Rekursionsgleichung gute Vermutungen braucht. Doch wie kommt man darauf? Ein Ansatz ist die Veranschaulichung durch einen Rekursionsbaum. Die Aufwandsklasse wird dann durch die Rekursionsbaummethode bestimmt. Das ist sehr nützlich, um eine Lösung zu raten, die danach durch eine andere Methode (z.B. Induktion) gezeigt wird. Rekursionsbäume sind besonders anschaulich bei Divide-and-Conquer-Algorithmen.

Spezialfall Divide and Conquer

Bei MergeSort sehen die Divide and Conquer Schritte wie folgt aus:

Divide: Zerteile eine Folge mit n Elementen in zwei Folgen mit je n/2 Elementen.
Conquer: Wenn die resultierende Folge 1 oder 0 Elemente enthält,dann ist sie sortiert. Ansonsten wende MergeSort rekursiv an.
Combine: Mische die zwei sortierten Teilfolgen.

$T(n):=\left\{{\begin{array}{ll}\Theta (1)&{\text{für }}(n\leq 1)\\D(n)+\alpha \cdot T(n/b)+C(n)&{\text{sonst}}\end{array}}\right.$

public List mergeSort(List f) {
  if (f.size() <= 1) {
    return f;
  } else {
    int m = f.size() / 2;
    List left = mergeSort(f.subList(0,m));
    List right = mergeSort(f.subList(m,f.size());
    return merge(left, right);
  }
}

$T(n):=\left\{{\begin{array}{ll}\Theta (1)&{\text{für }}(n\leq 1)\\2\cdot T(n/2)+\Theta (n)&{\text{sonst}}\end{array}}\right.$

Rekursionsbaum

Herleitung des Aufwandes

Die Grundidee ist das wiederholte Einsetzen der Rekursionsgleichung in sich selbst als Baum dargestellt. Das Ziel ist ein Muster zu erkennen. Bei einem Rekursionsbaum beschreibt ein Knoten die Kosten eines Teilproblems. Die Blätter sind die Kosten der Basis fällt T(0) und T(1). Der Aufwand bestimmt sich aus der Summe über alle Ebenen.

1. Ebene $c\cdot n$

2. Ebene $2\cdot {\frac {1}{2}}\cdot c\cdot n$

3. Ebene $4\cdot {\frac {1}{4}}\cdot c\cdot n$

....

n. Ebene $\Theta (1)\cdot n=\Theta (n)$

Der Aufwand berechnet sich nun wie folgt:

$T(n)=c\cdot n+2\cdot {\frac {1}{2}}\cdot c\cdot n+4\cdot {\frac {1}{4}}\cdot c\cdot n+2^{log_{2}n-1}\cdot {\frac {1}{2^{log_{2}n-1}}}\cdot c\cdot n+\Theta (n)$

=\sum _{i=0}^{log_{2}n-1}c\cdot n+\Theta (n)

=c\cdot n\cdot \sum _{i=0}^{log_{2}n-1}1+\Theta (n)

=c\cdot n\cdot log_{2}n+\Theta (n)

=\Theta (n\cdot log_{2}n)+\Theta (n)=\Theta (n\cdot log_{2}n)

Allgemein bestimmt sich der Aufwand T(n) durch die Summe des Aufwands je Ebene und des Aufwands der Blattebene.

Bezogen auf den gegebenen Rekursionsbaum wäre das $T(n)=3\cdot T(n/4)+c\cdot n^{2}$

Literatur

Da die Vorlesungsinhalte auf dem Buch Algorithmen und Datenstrukturen: Eine Einführung mit Java von Gunter Saake und Kai-Uwe Sattler aufbauen, empfiehlt sich dieses Buch um das hier vorgestellte Wissen zu vertiefen. Die auf dieser Seite behandelten Inhalte sind in Kapitel 8.3 zu finden.