Aufwandsanalyse von rekursiven Algorithmen

Auf dieser Seite wird der Aufwand von rekursiven Algorithmen untersucht.

public int fib(int n) { 
   if (n == 0 || n == 1) {
      return 1;
   } else {
      return fib(n-1) + fib(n-2);
   }
}

Wie ist nun der Aufwand für Fibonacci? Bei Rekursionsabbruch $f(n)=\Theta (1)+\Theta (1)$ und im Rekursionsfall $f(n)=\Theta (1)+???$ . Zur Bestimmung benutzen wir Rekursionsgleichungen.

Rekursionsgleichungen

Eine Rekursionsgleichung ist eine Gleichung oder Ungleichung, die eine Funktion anhand ihrer Anwendung auf kleinere Werte beschreibt.

Rekursionsgleichung für Fibonacci:

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

Lösung von Rekursionsgleichungen

Die Frage ist nun, welche Aufwandklasse T(n) beschreibt. Dies könnten alle möglichen Aufwandsklassen sein. Methoden um dieses Problem zu lösen, sind die vollständige Induktion und das Master-Theorem.

Spezialfall Divide and Conquer Algorithmus

Ein Divide-and-Conquer Algorithmus stellt im Allgemeinen eine einfache, rekursive Version eines Algorithmus dar und hat drei Schritte:

Divide: Unterteile das Problem in eine Zahl von Teilproblemen
Conquer: Löse das Teilproblem rekursiv. Wenn das

Teilproblem klein genug ist, dann löse das Teilproblem direkt (z.B. bei leeren oder einelementigen Listen)

Combine: Die Lösungen der Teilprobleme werden zu einer Gesamtlösung kombiniert.

Merge Sort ist beispielsweise ein Divide and Conquer Algorithmus.

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 Merge Sort rekursiv an.
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);
  }
}

Die dazugehörige Rekursionsgleichung lautet:

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

Im Allgemeinen ist die Rekursionsgleichung für Divide and Conquer Algorithmen:

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

mit D(n) als Aufwand für Divide, T(n/b) als Aufwand für Conquer und C(n) als Aufwand für Combine.

Ab- und Aufrunden

Die Rekursionsgleichung von MergeSort beschreibt den Aufwand für den schlechtesten Fall.

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

Aber die Annahme, dass n eine geeignete ganze Zahl ist ergibt normalerweise das gleiche Ergebnis wie eine beliebige Zahl mit Auf- bzw. Abrunden. Dies führt zur einfacheren Rekursionsgleichung:

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

Beispiel Binäre Suche

public List binarySearch(ArrayList<Integer> f, int e) {
  if (f.size() == 0) {
    return -1;
  } else {
    int m = f.size() / 2;
    if (f.get(m) == e) {
      return m;
    } else if (f.get(m) < e) {
      return binarySearch(f.subList(0, m), e);
    } else {
      return binarySearch(f.subList(m+1, f.size()), e);
    }
  }
}

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

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 7.3.4 zu finden.