Kurs:Algorithmen und Datenstrukturen/Vorlesung/Rekursionsbäume

Aus Wikiversity
Zur Navigation springen Zur Suche springen




Rekursionsbäume[Bearbeiten]

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[Bearbeiten]

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

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


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);
  }
}

Rekursionsbaum[Bearbeiten]

Rekursionsbaum

Herleitung des Aufwandes[Bearbeiten]

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.

Rekursionsbaum

1. Ebene

2. Ebene

3. Ebene

....

n. Ebene

Der Aufwand berechnet sich nun wie folgt:

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

Literatur[Bearbeiten]

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.


Vorheriges Thema.jpg Discussion R-3